最小生成樹演算法之Kruskal演算法

定義

克魯斯卡爾（Kruskal）演算法過程：構造最小生成樹（U,TE）

1. 置U的初值等於V（即包含有G中的全部頂點），TE的初值爲空集（即圖T中每一個頂點都構成一個連通分量）。
2. 將圖G中的邊按權值從小到大的順序依次選取：
 -  若選取的邊未使生成樹T形成迴路，則加入TE；
 -  否則捨棄，直到TE中包含(n-1)條邊爲止。

結構體定義

typedef struct sn
{
    int u; //當前頂點
    int v; //下一個頂點
    int w; //權值
}Edge;

Edge E[MAXV];

核心程式碼

kruskal演算法的c語言形式

void Kruskal(MatGraph g)
{  int i,j,u1,v1,sn1,sn2,k;
   int vset[MAXV];
   Edge E[MaxSize];		//存放所有邊
   k=0;				//E陣列的下標從0開始計
   for (i=0;i<g.n;i++)	//由g產生的邊集E
     for (j=0;j<g.n;j++)
        if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
	 {  E[k].u=i;  E[k].v=j;  E[k].w=g.edges[i][j];
	    k++;
	 }
   InsertSort(E,g.e);		//用直接插入排序對E陣列按權值遞增排序
   for (i=0;i<g.n;i++) 	//初始化輔助陣列
	vset[i]=i;
    k=1;				//k表示當前構造生成樹的第幾條邊
    j=0;				//E中邊的下標，初值爲0
while (k<g.n)		//生成的邊數小於n時回圈
  { 
     u1=E[j].u;v1=E[j].v;	//取一條邊的頭尾頂點
     sn1=vset[u1];
     sn2=vset[v1];		//分別得到兩個頂點所屬的集合編號
     if (sn1!=sn2)  		//兩頂點屬於不同的集合
     {  printf("  (%d，%d):%d\n",u1,v1,E[j].w);
        k++;		   	//生成邊數增1
        for (i=0;i<g.n;i++)  	//兩個集合統一編號
           if (vset[i]==sn2) 	//集合編號爲sn2的改爲sn1
		        vset[i]=sn1;
     }
     j++;			//掃描下一條邊
  }
}

Enjoy