【0】README

1）本文旨在給出?ReviewForJob——最小生成樹（prim + kruskal）源碼實現和分析， 還會對其用到的 技術 做介紹；

2）最小生成樹是對無向圖而言的：一個無向圖G 的最小生成樹是一個連通圖，且保證該連通圖 所含邊的權值和最小；

3）要知道?Prim算法（普利姆算法）的基本 idea 就是 迪杰斯特拉算法，下面會介紹，所以我會po 出 迪杰斯特拉算法的 相關介紹；

4）下面的內容（參見迪杰斯特拉算法）轉自?http://blog.csdn.net/pacosonswjtu/article/details/52125636?：其實，說白了：廣度優先搜索算法（計算無權最短路徑） 是基于 拓撲排序算法的，而?迪杰斯特拉算法（計算有權最短路徑） 是基于 廣度優先搜索算法或者說是它的變體算法；上述三者不同點在于：?拓撲排序算法 和 廣度優先搜索算法 使用了 循環隊列， 而迪杰斯特拉算法使用了 二叉堆優先隊列作為其各自的工具；相同點在于：他們都使用了 鄰接表來表示圖；所以?普利姆算法 也是基于 廣度優先搜索算法的，且要使用二叉堆優先隊列用于選取 權值最小的邊；

5）需要事先知道的是：尋找最小生成樹有兩種alg—— 普利姆算法 和 克魯斯卡爾算法，普利姆算法過程中有且只有一個連通圖，而克魯斯卡爾算法過程中 會形成多個 連通圖；且 克魯斯卡爾算法使用到了路徑壓縮，提高了find() 操作的效率，文末會講到；

【1】Prim算法（普利姆算法）?prim alg 源碼

1）intro：普利姆算法用于在 無向圖中尋找 最小生成樹，其基本idea 同 迪杰斯特拉算法，上面已經提及過了；

2）與迪杰斯特拉算法不同的地方在于： 權值更新操作，廢話不多說，上代碼；

補充）普利姆算法的結束標志：當 所有頂點的狀態都是已知（known==1）的時候，算法結束；

// 所有點相連的邊的權值最小. // adj:鄰接表（圖的標準表示方法）, table: 計算無權最短路徑的配置表，heap：用于選取最小權值的鄰接頂點的小根堆. void prim(AdjList adj, UnWeightedTable table, int startVertex, BinaryHeap heap) { int capacity=adj->capacity;Vertex* arrayVertex = adj->array;Vertex temp;Entry* arrayEntry = table->array;int index; // 頂點標識符(從0開始取)int adjVertex;struct HeapNode node;int weight;int i=0; // 記錄已知頂點個數（ known == 1 的 個數）.//step1(初始狀態): startVertex 頂點插入堆. startVertex 從1 開始取.node.vertex=startVertex-1; // 插入堆的 node.vertex 從 0 開始取，所以startVertex-1.node.weight=0;insert(heap, node); // 插入堆.arrayEntry[startVertex-1]->dv=0;arrayEntry[startVertex-1]->pv=0;// 初始狀態over.// step2: 堆不為空，執行 deleteMin操作. 并將被刪除頂點的鄰接頂點插入堆.while(!isEmpty(heap)){ if(i == capacity) // 當所有 頂點都 設置為 已知（known）時，退出循環. { break; } index = deleteMin(heap).vertex; // index表示鄰接表下標，從0開始取，參見插入堆的操作.arrayEntry[index]->known=1; // 從堆取出后，將其 known 設置為1.i++; // 記錄已知頂點個數（ known == 1 的 個數）.temp = arrayVertex[index]; while(temp->next) {adjVertex = temp->next->index; // 頂點index 的鄰接節點標識符adjVertex 從1開始取.weight = temp->next->weight; // 頂點index到其鄰接頂點 的權值.if(arrayEntry[adjVertex-1]->known == 0) // 注意: 下標是adjVertex-1, 且known==0 表明 adjVertex頂點還處于未知狀態,所以adjVertex插入堆.{// prim 算法的代碼版本.if(arrayEntry[adjVertex-1]->dv > weight ) // [key code] 當當前權值和 比 之前權值和 小的時候 才更新，否則不更新.{node.vertex=adjVertex-1; // 插入堆的 node.vertex 從 0 開始取.node.weight=weight;insert(heap, node); // 插入堆.arrayEntry[adjVertex-1]->dv = weight; // [also key code] arrayEntry[adjVertex-1]->pv=index+1; // index 從0開始取，所以index加1. }/* dijkstra 算法的代碼版本.if(arrayEntry[adjVertex-1]->dv > arrayEntry[index]->dv + weight ) // [key code] 當當前權值和 比 之前權值和 小的時候 才更新，否則不更新.{node.vertex=adjVertex-1; // 插入堆的 node.vertex 從 0 開始取.node.weight=weight;insert(heap, node); // 插入堆.arrayEntry[adjVertex-1]->dv = arrayEntry[index]->dv + weight; // [also key code] arrayEntry[adjVertex-1]->pv=index+1; // index 從0開始取，所以index加1. }*/} temp = temp->next;}//printWeightedtable(table, 1); // 取消這行注釋可以 follow 迪杰斯特拉 alg 的運行過程.} }

對權值更新的分析（Analysis）：

A1）普利姆算法的權值更新： 新權值== 其前驅頂點->該頂點的權值（weight）；

A2）迪杰斯特拉算法的權值更新：新權值== 其前驅的前驅頂點-> 前驅的權值（arrayEntry[index]->dv） + weight；

【2】Kruskal 算法（克魯斯卡爾算法）克魯斯卡爾源碼

1）intro：連續地按照最小的權選擇邊，并且當所選的邊不產生圈時就把它作為取定的邊；

2）克魯斯卡爾算法由多個連通圖：將多個連通圖進行合并，最終只有1個連通圖，當添加到 連通圖的邊足夠多時書法終止（如 頂點數目為7， 則當添加的邊數為6 則算法終止）；事實上，克魯斯卡爾算法就是要決定邊 應該添加還是應該放棄；

3）克魯斯卡爾算法用到的技術：

tech1）二叉堆優先隊列：用于選取權值最小的邊（deleteMin（binaryHeap）操作來完成）；

tech2）克魯斯卡爾算法就是要決定邊 應該添加還是應該放棄，這里用到了不相交集 ADT 的union/find 操作，當find(v1) 返回的集合標識 和 find(v2) 返回的集合標識不同時，則添加邊(v1,v2)；否則放棄添加；

// 克魯斯卡爾算法 用于尋找 最小生成樹. // 為什么這里沒有把 鄰接表作為參數傳進來，因為即使將其作為參數，其還是要轉化為 堆， // 所以，為了算法的簡潔性，在調用 kruskal() 方法前 就將 鄰接表轉化為 二叉堆優先隊列了. void kruskal(BinaryHeap heap, int* setArray, Edge* edgeSet, int edgeNum) // 當頂點數=7時，edgeNum=6 因為 7個頂點最多6條邊. {int i=0;Edge edge;int set1, set2;while(!isEmpty(heap) && i<edgeNum){edge = deleteMin(heap); // edge 不可能為空，因為heap 不為空（while循環）。set1 = find(setArray, edge->v1);set2 = find(setArray, edge->v2);// 克魯斯卡爾算法就是要決定邊 應該添加還是應該放棄if(set1 != set2) // 如果 v1 和 v2 不屬于同一個集合，邊就進行合并.{// setUnion begins.edgeSet[i++] = edge; // 添加邊. setArray[set2] = set1; //更新 edge->v2 的根的 集合標識. 而不能寫成setArray[edge->v2] = set1;// setUnion over.}} }

tech3）為了提高find() 操作的效率，使用到了 路徑壓縮。為什么需要路徑壓縮？ 因為集合合并涉及兩個操作：find 和 merge/setUnion 操作，又 find() 操作的執行效率取決于 樹的高度，所以要進行路徑壓縮，減少樹的高度（路徑長度）（補充：路徑壓縮定義——設操作是 find(x)，此時路徑壓縮的效果是 從 x 到 根的路徑上的每一個節點（包括x，但不包括根）都作為根的直接兒子） 路徑壓縮基礎參見?路徑壓縮基礎知識

// 尋找 index標識的 頂點 所在的集合. // find() 涉及到路徑壓縮，路徑壓縮 基于 棧來實現（先進后出）. int find(int* setArray, int index) {int temp = index;int i=0; while(index != setArray[index]){stack[i++] = index; // index 從 1 開始取，stack 的元素 也從 1 開始取.index = setArray[index]; // setArray 下標從1 開始.} // 下面進行路徑壓縮(基于棧的觀點). while(--i >= 0){setArray[ stack[i] ] = index;} return index; }

對以上代碼的分析（Analysis）：路徑壓縮是基于 不相交集 find 和 setUnion 操作，下面對其做分析

A1）起初，所有頂點都是一個集合，每個集合中只有一個頂點，有多少個頂點就有多少個集合，即setArray[i] = i（要知道0號下標不用的，這樣為了編程方便），setArray[i] 中保存的是 僅僅是集合的標志；

A2）對邊 執行 setUnion() 即合并之前，要執行find() 操作，查看 邊的兩個頂點 是否屬于同一個集合，好比 v1-weight-v2 == edge 這條邊， setArray[v1] == setArray[v2]? 如果它們返回的集合標識符相等，則放棄合并；否則將它們進行合并；

A3）合并也要分兩個步驟： step1）將邊添加到 edgeSet 集合中；step2）更新 任意一個頂點的根的集合 而不是 一個頂點的集合，這里是很重要的 ；什么叫做根？ 但 setArray[i] == i 的時候，我們認為 i標識所在的頂點叫做根；

看個合并荔枝）說了這么多，還不如一個荔枝來的快：再次提醒 當 setArray[i]==i 的時候，i標識的頂點才是根，才是集合的根，或是集合的標識；

看個荔枝）什么叫路徑壓縮？在源碼實現的測試用例中，通過堆的deleteMin 依次選擇權值最小的邊并添加到 edgeSet中，參考上述調試結果，我們知道選擇順序是 (v1, v4) (v6, v7)?(v3, v4)(v1, v2)??(v2, v4) (v1,v3) (v4, v7) (v3, v6) (v5, v7)；

下面我們依次來分析 什么叫做路徑壓縮：

step1）(v1,v4) 被添加后，setArray[4]=1,又 setArray[1]=1（滿足根的定義），所以v4 和v1 一樣屬于集合1；

step2）(v6, v7)被添加后，setArray[7]=6, 又 setArray[6]=6（滿足根的定義），所以 v7 和 v6 一樣屬于集合6；

step3）(v3, v4) 被添加后，setArray[4]=1，setArray[1]=3, setArray[3]=3；因為 頂點4的根是頂點1，所以其根要和頂點3 屬于同一個集合，則setArray[1]=3，下次find(4) 的路徑為 setArray[4]=1 -> setArray[1]=3 -> setArray[3]=3（滿足根的定義，over）

step4）(v1, v2)被添加后，setArray[2]=3，因為頂點3是頂點1 的 根；

step5）(v2,v4) v2 和 v4 屬于同一集合，放棄添加；但是我們發現 setArray[4]=3 了，之前setArray[4]=1的，看看之前的結構是 根3->1->4， 再看看之后的結構是 根3->4 , 根3->1，這就是路徑壓縮的一個荔枝，因為頂點4 離根3 近了，這就提高了 find的查找效率，以前find(4) 的路徑為2，現在的路徑為1 因為直接就找到 頂點4的根3了；再次提醒，有興趣的同學可以參考?路徑壓縮基礎知識

總結

以上是生活随笔為你收集整理的ReviewForJob——最小生成树（prim + kruskal）源码实现和分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。