while循環其實不是隻循環V-1次，因為如果找出的邊能夠形成環的話，這條邊并不是我們需要的邊，是以本次循環無效。while循環中其實包含了找出最小的功能，這個其實可以通過單獨的一個函數來實作。就是按邊長度升序來排列。
kruskal算法其實是一個找邊的算法，對于一V個頂點的圖，必定由V-1條邊構成一個最小生成樹，那麼按邊的權值周遊圖每一條邊。判斷如果添加這條選出的目前權最小的邊，圖中會不會生成一個環，如果生成環，則目前找到的這條邊無效，繼續找下一條權值最小邊。
每找出一條邊，相當于圖中合并了兩個連通部件（初始化是一個頂點算一個連通部件），是以找到V-1條邊就相當于是将原來分離的V個連通部件合并成一個更大的連通部件。
在兩個連通部件之間添加一條邊，會組成一個更大的連通部件，并且不存在環。
#include<iostream>
#include<malloc.h>
#include<queue>
#include <algorithm>
#include<stdlib.h>
#include<functional>
using namespace std;
#define maxNum 100 //定義鄰接舉證的最大定點數
#define maxWeight 1000000 //邊權最大值
int visited[maxNum][maxNum];//用來表示邊visited[i][j]是否被通路過，初始化都是0
int set[maxNum];
//頂點資訊
typedef struct
{
int id;
int dist;
}node;
//圖的鄰接矩陣表示結構
typedef struct
{
//char v[maxNum];//圖的頂點資訊
node v[maxNum];
int e[maxNum][maxNum];//圖的頂點資訊
int vNum;//頂點個數
int eNum;//邊的個數
}graph;
//函數聲明
void createGraph(graph *g);//建立圖g
void kruskal(graph *g);
void createGraph(graph *g)//建立圖g
cout<<"正在建立無向圖..."<<endl;
cout<<"請輸入頂點個數vNum:";
cin>>g->vNum;
//cout<<"請輸入邊的個數eNum:";
// cin>>g->eNum;
int i,j;
//構造鄰接矩陣，頂點到自身的距離是無窮大的。
cout<<"輸入鄰接矩陣權值："<<endl;
for(i=1;i<=g->vNum;i++)
for(j=1;j<=g->vNum;j++)
{
cin>>g->e[i][j];
if(g->e[i][j]==0)
{
g->e[i][j]=maxWeight;
}
}
}
void kruskal(graph *g)
{
cout<<"最小生成樹是："<<endl;
int k=1;
int i,j;
int a=1,b=1;
int min=g->e[a][b];
//初始化visited[][]
for(i=1;i<=g->vNum;i++)
for(j=1;j<=g->vNum;j++)
{
visited[i][j]=0;//表示邊i-j沒有被通路過
}
//初始化set[]
{
set[i]=i;
}
while(k<=g->vNum-1)//V-1次合并連通部件操作：union。v-1=e，就是查找出所有滿足最小生成樹的邊
//找出最小邊i->j
for(i=1;i<=g->vNum;i++)
for(j=1;j<=g->vNum;j++)
if(g->e[i][j]<min&&visited[i][j]==0)
{
min=g->e[i][j];
a=i;
b=j;
}
visited[a][b]=1;
visited[b][a]=1;
min=maxWeight;
if(set[a]!=set[b])//a b不在一個連通分量中，則合并
k++;//表中找到了一條合适的邊
cout<<a<<"->"<<b<<endl;
//合并集合。将連同部件b合并到連同部件a中去。
int temp_set=set[b];
for(i=1;i<=g->vNum;i++)
if(set[i]==temp_set)
set[i]=set[a];//将b合并到a中去。
cout<<set[i]<<" ";
cout<<endl;
}
int main()
graph *g;
g=(graph*)malloc(sizeof(graph));
createGraph(g);
kruskal(g);
int i;
cout<<set[i]<<" ";
cout<<endl;
system("pause");
return 0;
}
/*
正在建立無向圖...
請輸入頂點個數vNum:
6
輸入鄰接矩陣權值：
0 5 6 4 0 0
5 0 1 2 0 0
6 1 0 2 5 3
4 2 2 0 0 4
0 0 5 0 0 4
0 0 3 4 4 0
最小生成樹是：
2->3
1 2 2 4 5 6
2->4
1 2 2 2 5 6
3->6
1 2 2 2 5 2
1->4
1 1 1 1 5 1
5->6
5 5 5 5 5 5
請按任意鍵繼續. . .
*/
為了是程式更加清晰，将合并集合的方法單獨提取出來。代碼執行個體如下：
void union_set(graph *g,int a,int b)
//合并集合。将連同部件b合并到連同部件a中去。
int temp_set=set[b];
if(set[i]==temp_set)
set[i]=set[a];//将b合并到a中去。
修改以後原來的程式隻稍作修改即可，在void kruskal(graph *g)中作如下修改：
if(set[a]!=set[b])//a b不在一個連通分量中，則合并
k++;//表中找到了一條合适的邊
cout<<a<<"->"<<b<<endl;
union_set(g,a,b);//合并集合。
本文轉自xwdreamer部落格園部落格，原文連結：http://www.cnblogs.com/xwdreamer/archive/2011/06/15/2297001.html，如需轉載請自行聯系原作者
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)