2010年10月28日 星期四

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

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

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

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

完成圖 : 
 

範例代碼 : 
  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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...