最小生成樹：Prim算法

構造連通圖的最小代價生成樹

(連通所有頂點且帶權邊之和最小)

Prim算法是以某頂點為起點,逐漸找各頂點上最小權值的邊來建構最小生成樹

下面最小生成樹拍攝自教材《大話資料結構》

無向圖

頂點數組

鄰接矩陣

使用Prim創造最小生成樹過程

假設從頂點 V 0 V_0 V0​ 出發(圖中任何一頂點均可)，頂點 V 1 , V 5 V_1,V_5 V1​,V5​到頂點 V 0 V_0 V0​兩個權值分别為10，11中，是以對于頂點 V 0 V_0 V0​來說，頂點 V 1 V_1 V1​到頂點 V 0 V_0 V0​的權值最小，該權值為10，将其對應的邊 ( V 0 , V 1 ) (V_0,V_1) (V0​,V1​)納入最小生成樹

頂點 V 1 V_1 V1​的各邊權值 18,12,16以及11進行比較，其中權值最小為 11，将邊 ( V 0 , V 5 ) (V_0,V_5) (V0​,V5​)納入最小生成樹

接着從頂點 V 5 V_5 V5​的各邊權值17,26以及18，12，16進行比較，其中權值最小為 12，将邊 ( V 1 , V 8 ) (V_1,V_8) (V1​,V8​)納入最小生成樹

接着從頂點 V 8 V_8 V8​的各邊權值8,21以及18,16,17,26進行比較，其中權值最小為 8，将邊 ( V 2 , V 8 ) (V_2,V_8) (V2​,V8​)納入最小生成樹

接着從頂點 V 2 V_2 V2​的各邊權值22以及21,16,17,26進行比較，其中權值最小為 16，将邊 ( V 1 , V 6 ) (V_1,V_6) (V1​,V6​)納入最小生成樹

接着從頂點 V 6 V_6 V6​的各邊權值24,19以及22,21,26進行比較，其中權值最小為 19，将邊 ( V 6 , V 7 ) (V_6,V_7) (V6​,V7​)納入最小生成樹

接着從頂點 V 7 V_7 V7​的各邊權值16,7以及22,21,24,26進行比較，其中權值最小為 7，将邊 ( V 7 , V 4 ) (V_7,V_4) (V7​,V4​)納入最小生成樹

接着從頂點 V 4 V_4 V4​的各邊權值20以及22,21,24,16進行比較，其中權值最小為16，将邊 ( V 7 , V 3 ) (V_7,V_3) (V7​,V3​)納入最小生成樹

至此圖中全部頂點全部連通，最小生成樹構造完成

集合 U U U為頂點集 V V V的子集

集合 V − U V-U V−U為不包含集合 U U U中元素的頂點集

集合 V − U V-U V−U中頂點與集合 U U U頂點滿足在圖中已構成邊，從這些權值對應的邊中選出權值最小的邊 (此邊是由前面兩個集合中各取一個頂點組成的)，将滿足此條件的集合 V − U V-U V−U中的頂點加入到集合 U U U中

k是最新closedge數組中最小lowcost值對應頂點的下标

最小邊 ( u 0 , v 0 ) (u_0,v_0) (u0​,v0​)是滿足以上條件的兩個頂點構成的邊【 u 0 ∈ U u_0 \in U u0​∈U， v 0 ∈ V − U v_0 \in V-U v0​∈V−U】

構造最小生成樹過程輔助數組中各分量的值

鄰接矩陣存儲表示

#define MaxInt 32767	//表示極大值,即無窮大
#define MVNum 100		//最大頂點數
typedef char VerTexType;	//頂點的資料類型為字元型
typedef int ArcType;	//邊的權值類型為整型
typedef struct{
	VerTexType vexs[MVNum];	//頂點表
	ArcType arcs[MVNum][MVNum];	//邊表（鄰接矩陣）
	int vexnum,arcnum;	//圖的目前頂點數和邊數
}AMGraph;

           

輔助數組closedge定義

typedef struct{
	VerTexType adjvex;	//最小邊在集合U中的頂點
	ArcType	lowcost;	//最小邊對應的權值
}closedge[MVNum];
           

Prim算法

無向網G以鄰接矩陣形式存儲，從頂點u出發構造G的最小生成樹T，輸出T的各條邊

void MiniSpanTree_Prim(AMGraph G, VerTexType u){ //u為頂點資訊
	k=LocateVex(G,u);	//k為頂點u的下标
	for(int j=0; j<G.vexnum; ++j)	//對于集合V-U的每一個頂點Vj，初始化closedge[j]
		if(j!=k)
			closedge[j]={u,G.arcs[k][j]};	//closedge[]={adjvex,lowcost}
	closedge[k].lowcost=0;	//初始化,U={u}
	for(int i=1; i<G.vexnum; ++i){	//選擇其餘n-1個頂點
		k=Min(closedge);	//求出T的下一個結點：第k個頂點，closedge[k]中存有最小邊
		u0=closedge[k].adjvex;	//u0為最小邊的一個頂點，u0 ∈ U
		v0=G.vexs[k];	//v0為最小邊的另一個頂點，v0 ∈ V-U
		cout << u0 << v0;	//輸出目前的最小邊(u0,v0)
		closedge[k].lowcost=0;	//第k個頂點并入集合U
		for(int j=0; j<G.vexnum; ++j)
			if(G.arcs[k][j]<closedge[j].lowcost)	//新頂點并入集合U後重新選擇最小邊
				closedge[j]={G.vexs[k],G.arcs[k][j]};	//closedge[]={adjvex,lowcost}
	}
}
           

頂點數組vexs

鄰接矩陣arcs

上圖過程對下圖表中内容

進入for循環開始對其餘 n − 1 n-1 n−1個頂點進行分析

如下寫出對第二個頂點的分析

上圖過程對下圖表中内容