文章目錄

• 最小生成樹
• 普裡姆算法
• 克魯斯卡爾算法

  

最小生成樹

  假設要在 n 個城市之間建立通信聯絡網，則連通 n 個城市隻需要 n-1 條線路。這時，自然會考慮這樣一個問題，如何在最節省經費的前提下建立這個通信網絡。

  可以用連通網來表示 n 個城市以及 n 個城市間可能設定的通信線路，其中網的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權值表示相應的代價。對于 n 個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網。現在，我們要選擇這樣一棵生成樹，也就是使總的耗費最少。這個問題就是構造連通網的最小代價生成樹(簡稱為最小生成樹)的問題。一棵生成樹的代價就是樹上各邊的代價和。

  構造最小生成樹可以有多種算法。其中多數算法利用了最小生成樹的下列一種簡稱為 MST 的性質：假設 N=(V, {E}) 使一個連通網，U 是頂點集 V 的一個非空子集。若 (u,v) 是一條具有最小權值(代價)的邊，其中 u∈U，v∈V-U，則必存在一棵包含邊 (u, v) 的最小生成樹。

普裡姆算法

算法思路：

  假設 N=(V, {E}) 是連通網，TE 是 N 上最小生成樹中邊的集合。算法從 U={ u0 }(u0∈V)，TE={ } 開始，重複執行下述操作：在所有 u∈U，v∈V-U 的邊 (u, v)∈E 中找一條代價最小的邊 (u0, v0) 并入集合 TE，同時 v0 并入 U，直至 U=V 為止。此時 TE 中必有 n-1 條邊，則 T=(V, { TE }) 為 N 的最小生成樹。

1. 将連通網中的所有頂點分為兩類（假設為 A 類和 B 類）。初始狀态下，所有頂點位于 B 類；
2. 選擇任意一個頂點，将其從 B 類移動到 A 類；
3. 從 B 類的所有頂點出發，找出一條連接配接着 A 類中的某個頂點且權值最小的邊，将此邊連接配接着的 A 類中的頂點移動到 B 類；
4. 重複執行第 3 步，直至 B 類中的所有頂點全部移動到 A 類，恰好可以找到 N-1 條邊。

  實作這個算法需附設一個輔助數組，以記錄從 U 到 V-U 具有最小代價的邊。

  初始狀态，由于 U={v1}，則 V-U 中各頂點的最小邊，即為從依附于頂點 v1 的各條邊中，找到一條代價最小的邊 (u0, v0)=(1, 3) 為生成樹上的第一條邊，同時将 v0(=v3) 并入集合 U。然後修改輔助數組中的值。首先将 closedge[2].lowcost 改為 ‘0’，以示頂點 v3 已并入 U。然後，由于邊 (v3, v2) 上的權值小于 closedge[1].lowcost，則需修改 closedge[1] 為邊 (v3, v2) 及其權值。同理修改 closedge[4] 和 closedge[5]。依次類推，直到 U=V。假設以二維數組表示網的鄰接矩陣，且令兩個頂點之間不存在的邊的權值為機内允許的最大值。

void MiniSpanTree_PRIM(MGraph G, VertexType u){
	//用普裡姆算法從第u個頂點出發構造網G的最小生成樹T，輸出T的各條邊 
	//記錄從頂點集U和V-U的代價最小的邊的輔助數組定義： 
	//	struct{
	//		VertexType adjvex;
	//		VRType lowcost;
	//	}closedge[MAX_VERTEX_NUM];
	k = LocateVex(G, u);
	for(j=0;j<G.vexnum;j++)//輔助數組初始化 
		if(j != k)
			closedge[j] = {u, G.arcs[k][j].adj};
	closedge[k].lowcost = 0;//初始，U={u} 
	for(i=1;i<G.vexnum;i++){//選擇其餘G.vexnum-1個頂點 
		k = mininum(closedge);//求出T的下一個結點：第k頂點 
		//此時closedge[k].lowcost =  
		//		MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }
		printf(closedge[k].adjvex, G.vexs[k]);//輸出生成樹的邊 
		closedge[k].lowcost = 0;//第k頂點并入U集 
		for(j=0;j<G.vexnum;j++){
			if(G.arcs[k][j].adj < closedge[j].lowcost)//新頂點并入U後重新選擇最小邊 
				closedge[j] = {G.vexs[k], G.arcs[k][j].adj};
		}
	}
}
           

  普裡姆算法的時間複雜度為 O(n2)，與網中的變數無關，是以适用于求邊稠密的網的最小生成樹。

  而克魯斯卡爾算法恰恰相反，它的時間複雜度為 O(eloge)(e 為網中邊的數目)，是以它相對于普裡姆算法而言，适合于求邊稀疏的網的最小生成樹。

克魯斯卡爾算法

算法思路：

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

  克魯斯卡爾算法構造最小生成樹的條件：（1）n 個頂點，n-1 條邊；（2）所有的頂點要連通；（3）不能出現環。

  1，2，3，4 的 4 條邊由于滿足上述條件，則先後被加入到 T 中，代價為 5 的兩條邊 (v1, v4) 和 (v3, v4) 被舍去。因為它們依附的兩頂點在同一連通分量上，它們若加入 T 中，則會使 T 中産生回路，而下一條代價(=5)最小的邊(v2,v3)聯絡兩個連通分量，則可加入 T。由此，構造成一棵最小生成樹。

  上述算法至多對 e 條邊各掃描一次，假若以“堆”來存放網中的邊，則每次選擇最小代價的邊僅需 O(loge) 的時間(第一次需 O(e))。又生成樹 T 的每個連通分量可看成是一個等價類，則構造 T 加入新的邊的過程類似于求等價類的過程，由此可以 6.5 節介紹的 MFSet 類型來描述 T，使構造 T 的過程僅需 O(eloge) 的時間，由此，克魯斯卡爾算法的時間複雜度為 O(eloge)。