【0】README

0.1） 本文總結(jié)于 數(shù)據(jù)結(jié)構(gòu)與算法分析， 源代碼均為原創(chuàng)， 旨在 理解 Kruskal（克魯斯卡爾）算法 的idea 并用 源代碼加以實(shí)現(xiàn)；
0.2）最小生成樹的基礎(chǔ)知識(shí)，參見 http://blog.csdn.net/pacosonswjtu/article/details/49947085

---

【1】 Kruskal 算法（使用到了不相交集ADT的union/find 操作）

1.1）第二種貪婪策略是： 連續(xù)地按照最小的權(quán)選擇邊， 并且當(dāng)所選的邊不產(chǎn)生圈時(shí)就可以吧它作為取定的邊；
1.2）形式上， Kruskal算法是在處理一個(gè)森林——樹的集合。 開始的時(shí)候， 存在 |V|顆單節(jié)點(diǎn)樹， 而添加一邊則將兩棵樹合并成一顆樹， 當(dāng)算法終止的時(shí)候就只有一棵樹了， 這顆樹就是最小生成樹；
1.3）Kruskal算法的執(zhí)行步驟， 如下圖所示，看個(gè)荔枝：

對(duì)上圖的分析（Analysis）：

• A1）當(dāng)添加到森林中的邊足夠多時(shí)算法終止， 實(shí)際上， 算法就是要決定邊（u, v）應(yīng)該添加還是放棄。（前一章節(jié)中的 Union/Find 算法在這里適用）

1.4）我們用到了一個(gè)恒定的事實(shí)：在算法實(shí)施的任意時(shí)刻，兩個(gè)頂點(diǎn)屬于同一個(gè)集合當(dāng)且僅當(dāng)它們?cè)诋?dāng)前的森林中連通；因此， 每個(gè)頂點(diǎn)最初是在它自己的集合中；

• 1.4.1） 如果u 和 v 在同一個(gè)集合中， 那么連接它們的邊就要放棄， 因?yàn)橛捎谒鼈円呀?jīng)連通 了，如果再添加一條邊（u, v）就會(huì)形成一個(gè)圈了。
• 1.4.2）如果這兩個(gè)頂點(diǎn)不在同一個(gè)集合中， 則將該邊加入， 并對(duì)包含頂點(diǎn)u 和 v 的這兩個(gè)集合實(shí)施一次合并。
• 1.4.3）容易看到，這樣將保持集合不變性， 因?yàn)橐坏┻?#xff08;u, v）添加到生成森林中， 若w連通到 u 而 x連通到v， 則x 和 w 必然是連通的， 因此屬于相同集合 ；

1.5）固然，將邊排序可便于選取，不過，用線性時(shí)間建立一個(gè)堆則是更好的想法；

• 1.5.1）此時(shí)， deleteMin 將使得邊依序得到測(cè)試。 典型情況下， 在算法終止前只有一小部分邊需要測(cè)試， 盡管測(cè)試所有的邊的情況是有可能的；例如，還有一個(gè)頂點(diǎn) v8以及值為100的邊（v5, v8），那么所有的邊都會(huì)要考察到；

1.6）因?yàn)橐粭l邊由3個(gè)部分的數(shù)據(jù)組成， 所以在某些機(jī)器上吧優(yōu)先隊(duì)列實(shí)現(xiàn)成指向邊的指針數(shù)組比實(shí)現(xiàn)成邊的數(shù)組更為有效。

• 1.6.1）這種實(shí)現(xiàn)的 效果在于， 為重新排列堆， 需要移動(dòng)的只有那些指針， 而大量的記錄則不必移動(dòng)；

1.7）時(shí)間復(fù)雜度：該算法的最壞情形運(yùn)行時(shí)間為 O（|E|log|E|）， 它受堆操作控制。 注意， 由于 |E|=O(|V|^2)， 因此這個(gè)運(yùn)行時(shí)間實(shí)際上是 O（|E|log|V|）。在實(shí)踐中， 該算法要比這個(gè)時(shí)間界指示的時(shí)間快得多；

---

【2】source code + printing results（將我的代碼打印結(jié)果 同 “1.3” 上圖中的手動(dòng)模擬的 Kruskal 算法的結(jié)果進(jìn)行比較，你會(huì)發(fā)現(xiàn)， 它們的結(jié)果完全相同，這也證實(shí)了我的代碼的可行性）

2.0）code specification：

• s1）本代碼采用了優(yōu)先隊(duì)列（二叉小根堆）來升序選取邊；
• s2）本代碼采用了用到了不相交集ADT的 find和setUion 操作來對(duì)邊的兩個(gè)vertexes 進(jìn)行union 操作以及更新它們的根；
• s3）對(duì)于根的初始化，我是這樣初始化的—— parent[0]=-1,parent[1]=-2, parent[2]=-3, parent 說白了，就是 set的 一個(gè) index， 所以開始肯定是不一樣的； 然后，在union的時(shí)候，我只要檢查是否 i == -parent[i]-1 就可以知道 它是否是樹的根；
• s4） 在合并的時(shí)候，要對(duì)邊的兩個(gè)頂點(diǎn) start 和 end 的 parent做update， 這里涉及到4種情況—— start為根且end不為根；start為根且end為根；start為不為根且end為根；start不為根且end不為根； （干貨，本代碼的重中之重以及新穎之處）

2.1）download source code： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p240_kruskal
2.2）source code at a glance（for complete code , please click the given link above）：

#include <stdio.h> #include "binaryheap.h"// allocate memory for the vertexes with size Vertex* makeEmptyVertexes(int size) {Vertex *array; int i;array = (Vertex*)malloc(size * sizeof(Vertex)); if(!array){Error("out of space, from func makeEmptyVertexes");return NULL;} // initializing the set index towards every vertex with its array indexfor(i = 1; i <= size; i++)array[i-1] = -i;return array; }void printParent(Vertex* vertexes, int size) {int i;printf("\n\n\t the parent of every vertex at a glance");for(i=0; i<size; i++)printf("\n\t parent[%d] = %d", i, vertexes[i]); }int find(Vertex *parent, Vertex single){while (single >= 0)single = parent[single]; return single; }//judge whether the vertex index is the parent or not, also 1 or 0 //if the vertex under index is not the parent ,that's to say its parent is one of other vertexes int isParent(Vertex *parent, Vertex index) {return parent[index] == -index-1; }void setUnion(Vertex *parent, Vertex start, Vertex end) { if(isParent(parent, start) ) // start is the parent {if(!isParent(parent, end)) // but end is not the parentend = find(parent, end) + 1; // find the parent of endparent[start] = end; }else // start is not the parent {start = -find(parent, start) - 1; // find the parent of startif(!isParent(parent, end)) // but end is not the parentend = find(parent, end) + 1; // find the parent of endparent[end] = start;} }void kruskal(BinaryHeap bh, int vertexNum) {int counter;int set1;int set2; Vertex start;Vertex end;Vertex* parent;ElementType singleEdge; counter = 0; parent = makeEmptyVertexes(vertexNum);while(counter < vertexNum - 1){singleEdge = deleteMin(bh);start = singleEdge.start;end = singleEdge.end;set1 = find(parent, start);set2 = find(parent, end);// find the set of vertex start and endif(set1 != set2){ setUnion(parent, start, end);counter++;printf("\n\t weight(v%d,v%d) = %d", singleEdge.start+1, singleEdge.end+1, singleEdge.weight);} }printParent(parent, vertexNum);printf("\n\n\t"); }int main() { BinaryHeap bh;ElementTypePtr temp; int vertexNum;int size = 7;int capacity;int i;int j; int adjTable[7][7] = {{0, 2, 4, 1, 0, 0, 0},{2, 0, 0, 3, 10, 0, 0},{4, 0, 0, 2, 0, 5, 0},{1, 3, 2, 0, 7, 8, 4},{0, 10, 0, 7, 0, 0, 6},{0, 0, 5, 8, 0, 0, 1},{0, 0, 0, 4, 6, 1, 0},}; vertexNum = 7;capacity = vertexNum * vertexNum;bh = initBinaryHeap(capacity);temp = makeEmptyElement();printf("\n\n\t ====== test for kruskal alg building minimum spanning tree ======\n");//building binary heap with edge including 2 vertexs and its weight for(i = 0; i < size; i++){for(j = i+1; j < size; j++) if(adjTable[i][j]) { temp->start = i;temp->end = j;temp->weight = adjTable[i][j]; insertHeap(temp, bh); // insertAdj the adjoining table over}}kruskal(bh, vertexNum);return 0; } // allocate memory for the array with size ElementTypePtr *makeEmptyArray(int size) {ElementTypePtr *array;int i;array = (ElementTypePtr*)malloc(size * sizeof(ElementTypePtr)); if(!array){Error("out of space, from func makeEmptyArray");return NULL;}for(i=0; i<size; i++) array[i] = makeEmptyElement(); return array; }// allocate memory for the single element ElementTypePtr makeEmptyElement() {ElementTypePtr temp;temp = (ElementTypePtr)malloc(sizeof(ElementType));if(!temp){Error("out of space, from func makeEmptyElement!");return NULL;}return temp; }

2.3）printing results：

總結(jié)

以上是生活随笔為你收集整理的最小生成树——Kruskal（克鲁斯卡尔）算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。