[ 資料結構 小學堂 ] 圖形結構 : 擴張樹 - 求最小成本擴張樹 (Kruskal 演算法)

Kruskal 演算法 : 
Kruskal 演算法是將各邊線依權值大小由小到大排列, 接著從權值最低的邊開始架構最小的成本擴張樹, 如果加入的邊會造成迴路則捨棄不用, 直到加了 n-1 個邊為止. 這個方法看似不難, 我們直接來看如何以 K 氏法得到範例下圖中的最小成本擴張樹 : 
 
步驟一 : 將所有邊線的成本列出並由小到代排序 : 
 

步驟二 : 選擇成本最低的一條邊做為架構最小成本擴張樹的起點. Edge(B,C)->3 
步驟三 : 依步驟1所建立表格, 依序加入邊線. 
 

步驟四 : C-D 加入會形成迴路, 所以跳過. 
 

完成圖 : 
 

範例代碼 : 

view plaincopy to clipboardprint?

1. #include   
2.   
3. using namespace std;  
4.   
5. #define VERTS 6  //圖形頂點樹  
6. class edge {  
7. public:  
8.     int from, to;  
9.     int find, val;  
10.     class edge *next;  
11.     edge(){  
12.         from = -1;  
13.         to = -1;  
14.         find = 0;  
15.         val = -1;  
16.     }  
17. };  
18. typedef class edge enode;  
19. typedef edge* penode;  
20. int v[VERTS+1];  
21. char ptrName[7] = {'-','A','B','C','D','E','F'};  
22.   
23. penode _findmincost(penode head) { //搜尋成本最小的邊  
24.     int dv = 100;  
25.     penode ptr, retptr;  
26.     ptr = head;  
27.     while(ptr!=NULL) {  
28.         if(ptr->val < dv && ptr->find ==0) {  
29.             retptr = ptr;  
30.             dv = ptr->val;  
31.         }  
32.         ptr = ptr->next;  
33.     }  
34.     retptr->find = 1;  
35.     return retptr;  
36. }  
37.   
38. void _minTree(penode head) { // 最小成本擴張樹副程式  
39.     penode ptr, mceptr;  
40.     int result = 0;  
41.     ptr = head;  
42.     for(int i=0; i<=VERTS; i++)  
43.         v[i] = 0;  
44.     while(ptr!=NULL) {  
45.         mceptr = _findmincost(head);  
46.         if(v[mceptr->from] >0 && v[mceptr->to]>0) {  
47.             // 形成迴圈, 跳過  
48.         } else {  
49.             result++;  
50.             v[mceptr->from] = 1;  
51.             v[mceptr->to] = 1;  
52.             cout << "起始定點[" << ptrName[mceptr->from] << "]\t終止頂點[" <<  ptrName[mceptr->to] << "]\t路徑長度[" << mceptr->val << "]" << endl;  
53.         }  
54.         if(result==(VERTS-1))  
55.             break;  
56.     }  
57. }  
58.   
59. void main() {  
60.         // 成本陣列       
61.         int data[10][3] = {{1,2,6}, {1,6,12}, {1,5,10}, {2,3,3}, {2,4,5}, {2,6,8}, {3,4,7}, {4,6,11}, {4,5,9}, {5,6,16}};  
62.         penode head, ptr, newnode;  
63.         head = NULL;  
64.         cout << "建立圖形串列: " << endl;  
65.         for(int i=0; i<10; i++) {  
66.             newnode = new enode;  
67.             newnode->from = data[i][0];  
68.             newnode->to = data[i][1];  
69.             newnode->val = data[i][2];  
70.             newnode->next = NULL;  
71.             newnode->find = 0;  
72.             if(head == NULL) {  
73.                 head = newnode;  
74.                 ptr = head;  
75.             } else {  
76.                 ptr->next = newnode;  
77.                 ptr = ptr->next;  
78.             }  
79.         }  
80.         ptr = head;  
81.         while(ptr!=NULL) { // 列印圖形串列  
82.             cout << "起始定點[" << ptrName[ptr->from] << "]\t終止頂點[" <<  ptrName[ptr->to] << "]\t路徑長度[" << ptr->val << "]" << endl;  
83.             ptr = ptr->next;  
84.         }  
85.         cout << "建立最小成本擴張樹: " << endl;  
86.         _minTree(head);  
87.         delete head;  
88. }  

執行結果 : 

建立圖形串列:
起始定點[A] 終止頂點[ B] 路徑長度[6]
起始定點[A] 終止頂點[F] 路徑長度[12]
起始定點[A] 終止頂點[E] 路徑長度[10]
起始定點[ B] 終止頂點[C] 路徑長度[3]
起始定點[ B] 終止頂點[D] 路徑長度[5]
起始定點[ B] 終止頂點[F] 路徑長度[8]
起始定點[C] 終止頂點[D] 路徑長度[7]
起始定點[D] 終止頂點[F] 路徑長度[11]
起始定點[D] 終止頂點[E] 路徑長度[9]
起始定點[E] 終止頂點[F] 路徑長度[16]
建立最小成本擴張樹:
起始定點[ B] 終止頂點[C] 路徑長度[3]
起始定點[ B] 終止頂點[D] 路徑長度[5]
起始定點[A] 終止頂點[ B] 路徑長度[6]
起始定點[ B] 終止頂點[F] 路徑長度[8]
起始定點[D] 終止頂點[E] 路徑長度[9]

補充說明 :
* Wiki : 克魯斯克爾演算法

Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和Boruvka演算法等。三種演算法都是貪婪演算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效...

* [ 資料結構 小學堂 ] 圖形結構 : 擴張樹

This message was edited 9 times. Last update was at 16/05/2010 16:30:21