資料結構之最小生成樹

最小生成樹： 一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但隻有足以構成一棵樹的n-1條邊。這種構造連通網的最小代價生成樹稱為最小生成樹，詳見資料結構之圖（術語、存儲結構、周遊）。

求連通網的最小生成樹有兩種經典方法：普裡姆（Prime）算法和克魯斯卡爾（Kruskal）算法。

1、Prime算法

(1)算法描述

假設N=(V,{E})是連通網，TE是N上最小生成樹中邊的集合。從V中任選一個頂點u0，算法從U={u0}(u0∈V)，TE={}開始，重複執行以下步驟：

在所有u∈U、v∈V-U的邊(u, v)∈E中找一條代價最小的邊(u, vi)并入集合TE，同時将vi并入U，直至U=V為止。

此時TE中必有n-1條邊，則T={V,{TE}}即為N的最小生成樹。

需要用到兩個輔助數組：

lowcost[MAX_VEM]：存儲從U到V-U的具有最小代價邊上的權——lowcost[i] = Min{w(u, vi)|u∈U,vi∈V-U}

adjvex[MAX_VEM]：存儲從U到V-U的具有最小代價邊(u,vi)依附在U中的頂點u的下标——adjvex[i] = {u|lowcost[i] }

(2)執行個體

給定如下一個無向網：

根據上述prime算法描述，求其最小生成樹的過程如下：

最後得到如下最小生成樹：

(3)、算法代碼

//普裡姆(Prime)算法
void MiniSpanTree_Prime(Graph *g, VertexType u0)
{
	int min, i, j, k, v0;

	int adjvex[MAX_VEX];	//存儲從U到V-U的具有最小代價邊(u,vi)依附在U中的頂點u的下标
	                        //adjvex[i] = {u|lowcost[i] = Min{w(u, vi)|u∈U,vi∈V-U}}
	int lowcost[MAX_VEX];	//存儲從U到V-U的具有最小代價邊上的權——lowcost[i] = Min{w(u, vi)|u∈U,vi∈V-U}

	v0 = k = LocateVex(g, u0);	//定位開始的頂點u0在頂點數組中的下标号
	assert(k != -1);
	//adjvex[k] = k;	//初始化第一個頂點下标為k
	lowcost[k] = 0;	//初始,U={u}

	for (i = 0; i < g->vexNum; i++)	 
	{
		if (i != k)	//初始化除下标為k的其餘全部頂點
		{
			adjvex[i] = k;	//初始化都為頂點u對應的下标k
			lowcost[i] = g->arc[k][i];	//将頂點u與之有關的權值存入數組
		}
	}

	for (i = 0; i < g->vexNum; i++)
	{
		if (i == v0)
		{
			continue;
		}

		min = INFINITY;
		for (j = 0, k = 0; j < g->vexNum; j++)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)   //V-U中的全部頂點
			{
				min = lowcost[j];
				k = j;
			}
		}

		//printf("(%d,%d) ", adjvex[k], k);   //列印目前頂點中權值最小的邊:
		                                    //g->vexs[adjvex[k]]∈U,g->vexs[k]∈V-U
		printf("(%c,%c) ", g->vexs[adjvex[k]], g->vexs[k]);
		lowcost[k] = 0; //第k頂點并入U集

		for (j = 0; j < g->vexNum; j++)
		{
			if (lowcost[j] != 0 && g->arc[k][j] < lowcost[j])
			{
				lowcost[j] = g->arc[k][j];	//新頂點并入U後重新選擇最小邊
				adjvex[j] = k;
			}
		}
	}
	putchar('\n');
}
           

運作截圖：

分析：鄰接矩陣實作的普裡姆算法的時間複雜度為O(n^2)，與網中的邊數無關，适用于求邊稠密的網的最小生成樹。

2、Kruskal算法

(1)算法描述

假設連通網N={V,{E}}，令最小生成樹的初始狀态為隻有n個頂點而無邊的非連通圖T={V,{}}，圖中的每個頂點自成一個連通分量。在E中選擇代價最小的邊，若改邊依附的頂點落在T中不同的連通分量上，則将次邊加入到T中，否則舍去此邊而選擇下一條代價i最小的邊。以此類推，直到T中所有頂點都在同一個連通分量上為止。

Kruskal算法主要考慮是否會形成環路。在實際的代碼編寫中，一般采用邊集數組這一資料結構：

//邊集數組
#define  MAX_EDGE	100	//最大邊數
typedef struct  
{
	int begin;
	int end;
	EdgeType weight;
}Edge;
           

我們可以通過程式将鄰接矩陣通過程式轉化為邊集數組，并且對它們的按權值從小到大排序。如下圖所示。

（2）算法代碼

//将鄰接矩陣結構轉化成邊集
void Convert(Graph *g, Edge edge[])
{
	int i, j, k = 0;
	for (i = 0; i < g->vexNum; i++)
		for (j = i; j < g->vexNum; j++)	 //無向圖的鄰接矩陣是對稱的
			if (g->arc[i][j] < INFINITY)
			{
				edge[k].begin = i;
				edge[k].end = j;
				edge[k].weight = g->arc[i][j];
				k++;
			}
#if 0
			printf("排序前:\n");  
			printf("       \tbeign\tend\tweight\n");
			for(i = 0; i < k; i++)
			{							
				printf("edge[%d]\t%d(%c)\t%d(%c)\t%d\n", i, 
					edge[i].begin, g->vexs[edge[i].begin], 
					edge[i].end, g->vexs[edge[i].end], edge[i].weight);
			}
#endif
   InsertSort(edge, k);
#if 1
   printf("排序後:\n");  
   printf("       \tbeign\tend\tweight\n");
   for(i = 0; i < k; i++)
   {
	   printf("edge[%d]\t%d(%c)\t%d(%c)\t%d\n", i, 
		   edge[i].begin, g->vexs[edge[i].begin], 
		   edge[i].end, g->vexs[edge[i].end], edge[i].weight);
   }
#endif
}

//按權值大小對邊集數組edge從小至大排序
void InsertSort(Edge edge[], int k)
{
	int i, j;
	Edge tmp;

	for (i = 1; i < k; i++)
	{
		if (edge[i].weight < edge[i - 1].weight)
		{
			tmp = edge[i]; 
			for (j = i - 1; edge[j].weight > tmp.weight; j--)
			{
				edge[j + 1] = edge[j];
			}
			edge[j + 1] = tmp;
		}
	}
}

//查找連線頂點的尾部
int Find(int *parent, int f)
{
	while(parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}

//克魯斯卡爾算法實作
void MiniSpanTree_Kruskal(Graph *g)  
{
	int i, n, m;
	Edge edges[MAX_EDGE];    //定義邊集數組
	int parent[MAX_EDGE];     //定義一數組用來判斷邊與邊是否形成環

	//将鄰接矩陣轉化為邊集數組edges并按權值由小到大排序
	Convert(g, edges);

	for(i = 0; i < g->vexNum; i++)
	{
		parent[i] = 0;  //初始化數組值為0
	}

	for(i = 0; i < g->arcNum; i++)          //循環每一條邊
	{
		n = Find(parent, edges[i].begin);
		m = Find(parent, edges[i].end);
		if(n != m)      //假如n與m不等，說明此邊沒有與現有生成樹形成環路
		{
			parent[n] = m;  //将此邊的結尾頂點放入下為起點的parent數組中
			//表示此頂點已經在生成樹集合中
			//printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
			printf("(%c,%c) ", g->vexs[edges[i].begin], g->vexs[edges[i].end]);
		}
	}
	putchar('\n');
}
           

運作截圖：

不考慮鄰接矩陣或鄰接表轉化為邊集數組的時間開銷，克魯斯卡爾算法的Find函數由邊數e決定，時間複雜度為O(loge)，而外面有一個for循環e次，是以克魯斯卡爾算法的時間複雜度為O(eloge)，相對prime算法而言，适合于求邊稀疏的網的最小生成樹。

參考：這篇文章的url提示不對呀 “** 文章包含被禁用的url，無法儲存和釋出。” ，沒法給出參考連結了

            資料結構（C語言版）

完整的測試代碼：http://download.csdn.net/detail/u013071074/7467561