Kruskal算法的思想如下
- 假設(shè)有n個頂點的連通圖废岂。首先先構(gòu)造有頂點構(gòu)成的集合0浑娜，每個頂點都是一個集合，不含有任何邊底桂。
- 在邊找一個最小權(quán)值的邊
- 判斷這個邊的倆個頂點是否來自于兩個不同的集合植袍，若是就將它倆歸并為一個集合，然后將這個邊添加到要構(gòu)成的圖的集合中籽懦。
-
直到上述的邊的個數(shù)為頂點個數(shù)-1奋单；否則，重復(fù)2-3猫十；
算法構(gòu)成樹的過程如下：
如a圖所示的圖，下面是最小生成樹的構(gòu)造過程
image.png
（a）
(b)
(c)
(d)
(e)
(f)
在這里判斷一個邊的兩個頂點是不是屬于同一個集合呆盖，采用的是并查集的方式來實現(xiàn)
并查集的基本思想如下：
并查集可以用數(shù)組來和樹來實現(xiàn)拖云，在這里先講樹來實現(xiàn)。
1：樹實現(xiàn)并查集：
屬于同一個集合的結(jié)點擁有同一個根应又，圖示如下：
上面的樹中這些元素都屬于一個集合宙项，他們的根元素是1；
上面樹中元素屬于都屬于一個集合株扛，他們的根元素都是11尤筐；
兩個集合合并就是將一個集合連在另一個集合的根元素的下面就好了汇荐。如下圖所示：
那在合并集合的時候怎么合并集合呢？有沒有想過盆繁，如下圖所示的集合
一個樹的高度很大掀淘，一個樹的高度很小，這倆個集合在合并的時候要把高度小的集合合并在高度大的集合中油昂。因為在合并集合中的元素的時候革娄，首先要查找這個結(jié)點屬于那個結(jié)點，若是將高度高的集合合并在高度小的集合中冕碟，就會增加查找的時間拦惋，增加程序的時間復(fù)雜度。
數(shù)組實現(xiàn)并查集
基本思想就是安寺，在屬于一個集合的數(shù)據(jù)都用一個數(shù)據(jù)來表示就好厕妖，在合并集合的時候，就將兩個集合用一個數(shù)據(jù)來表示就好了挑庶，
如下圖：
有0——7個數(shù)據(jù)言秸；剛開始的時候他們都是一個集合，單獨的個體挠羔，每個的根都是自己本身井仰，-1表示他們都是單獨個個體，是個根破加，在查找根結(jié)點的時候就是一個判斷依據(jù)俱恶，只要對應(yīng)的數(shù)據(jù)項是負數(shù)，那就說明這個是根范舀；現(xiàn)在將1和2合并為一個集合如下圖：
將1對應(yīng)數(shù)據(jù)項和2對應(yīng)的數(shù)據(jù)項合并在一起合是，放在1對應(yīng)的數(shù)據(jù)項中，在這里面就是-1+-1锭环；將2對應(yīng)的數(shù)據(jù)項改為1聪全，表示它的根現(xiàn)在是1；這就是一個集合辅辩。
現(xiàn)在將4难礼，5歸為一個集合如下圖：
原理和上面的一樣
現(xiàn)在講3添加到2所集合中如下圖：
首相查找2的根，發(fā)現(xiàn)是1玫锋，然后在查找3的根蛾茉，發(fā)現(xiàn)是3，然后在1對應(yīng)的數(shù)據(jù)項中加上3對應(yīng)的數(shù)據(jù)項撩鹿。也就是-2+-1谦炬；然后將3對應(yīng)的數(shù)據(jù)項改為-1；
現(xiàn)在將5所在的集合和3所在的集合合并在一塊如下圖：
先查找5所在的根結(jié)點，發(fā)現(xiàn)是是4键思；現(xiàn)在在查找3所在的結(jié)點础爬，發(fā)現(xiàn)是1；然后還是是和之前一樣相加吼鳞。將4對應(yīng)的數(shù)據(jù)項和1對應(yīng)的數(shù)據(jù)項相加看蚜，合并兩個根就好，然后將4對應(yīng)的數(shù)據(jù)項改為1赖条；
現(xiàn)在6加到5所在的集合中如下圖：
查找5所在的集合失乾，5對應(yīng)的數(shù)據(jù)項是4，4對應(yīng)的數(shù)據(jù)項是1纬乍，1對應(yīng)的數(shù)據(jù)項是負數(shù)碱茁，說明這個是根，然后還是相加仿贬，還是合并纽竣；就好了
</br>
好了，并查集講完了接下來就是樹了
算法的流程圖如下：
程序如下：
#include <iostream>
using namespace std;
typedef struct node {
int start;//邊的起點
int end;//邊的終點
int wieght;//邊的權(quán)重
}node;
class Graph{
private:
node *edge; //邊的數(shù)組
int edgeNum;//邊的個數(shù)
int vertexNum;//頂點的個數(shù)
int* unionset;//并查集茧泪，頂點的集合
#pragma 下面的這幾個private函數(shù)都是并查集的函數(shù)
int findRoot(int node);//找根
void unionSet(int node1,int node2);//合并倆結(jié)點成為一個集合
bool isaSet(int node1,int node2);//判斷倆結(jié)點在沒在一個集合中
public:
Graph(int size,int vertexNum);
void create();
void sort();//冒泡法按照權(quán)值從大到小的順序排序蜓氨；
void kuscal();//kruskal算法；
void print();//輸出邊的數(shù)組和 頂點的集合队伟，
};
void Graph::print(){
cout<<"unionSet-----------------------------------------------------\n";
for (int i = 0; i<vertexNum+1; i++) {
cout<<i<<":"<<unionset[i]<<endl;
}
cout<<"unionset______________________________________________________\n";
for (int i =0; i<2; i++) {
cout<<endl;
}
cout<<"edge----------------------------------------------------------\n";
for (int i = 0; i<edgeNum; i++) {
cout<<"("<<edge[i].start<<","<<edge[i].end<<","<<edge[i].wieght<<")";
}
cout<<endl;
cout<<"edge__________________________________________________________\n";
}
//看是否在同一個集合穴吹，如果在一個集合，返回True嗜侮，否則返回false港令；
bool Graph::isaSet(int node1, int node2){
return findRoot(node1)==findRoot(node2) ? true : false;
}
//把node2添加到node1集合中
void Graph::unionSet(int node1, int node2){
int root1 = findRoot(node1);
int root2 = findRoot(node2);
unionset[root1]+=unionset[root2];
unionset[root2] = root1;
}
void Graph::sort(){
for (int i = 0; i<edgeNum -1; i++) {
for (int j = 0; j<edgeNum-1-i; j++) {
if(edge[j].wieght < edge[j+1].wieght){
int temp = edge[j].wieght;
int start = edge[j].start;
int end = edge[j].end;
edge[j].wieght = edge[j+1].wieght;
edge[j+1].wieght = temp;
edge[j].start = edge[j+1].start;
edge[j+1].start = start;
edge[j].end = edge[j+1].end;
edge[j+1].end = end;
}
}
}
print();
}
int Graph::findRoot(int node){
int root = node;
while (unionset[root] >= 0) {
root = unionset[root];
}
return root;
}
Graph::Graph(int size,int vertexNum){
edge = new node[size];
edgeNum = size;
this->vertexNum = vertexNum;
/*
1:一般來說，多申請一個锈颗，這樣有利于數(shù)據(jù)的統(tǒng)一
*/
unionset = new int[vertexNum+1];
for (int i = 0; i<vertexNum+1; i++) {
unionset[i]= -1;
}
}
void Graph::create(){
cout<<"input edge start and end and widght\n";
for (int i = 0; i<edgeNum; i++) {
cin>>edge[i].start>>edge[i].end>>edge[i].wieght;
}
}
void Graph::kuscal(){
sort();
int edgeNum1 = 0;//找到的滿足要求的邊的個數(shù)
int sum = 0;//找的滿足要求的邊的權(quán)重和?
int i = edgeNum-1;//控制邊數(shù)組的下標顷霹，從后往前取，最小值在后面
while (edgeNum1 != this->vertexNum-1 ) {
int start = edge[i].start;
int end = edge[i].end;
if( isaSet(start, end) == false){
unionSet(start, end);
edgeNum1++;
sum+=edge[i].wieght;
}
I--;
}
cout<<"sum"<<sum<<endl;
}
int main(){
Graph a(8, 6);
a.create();
a.print();
a.kuscal();
a.print();
}
輸入如下：
輸出如下：
