程式扎記: [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤

標籤

2010年10月25日 星期一

[ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤

前言 : 
樹的追蹤目的是欲拜訪樹的每一節點一次, 可用的方法有中序, 前序與後序等三種. 而圖形追蹤定義如下 : 
一圖形 G=(V,E), 存在某一頂點 v, 我們希望從v 開始並經由此節點的相鄰節點而去拜訪G 中其他節點, 這稱之為圖形追蹤.

也就是從某一頂點V1 開始, 走訪可以經由V1 到達的頂點, 接著再走訪下一個頂點直到全部的頂點走訪完畢為止. 在走訪的過程中可能會重複過某些頂點及邊線. 經由圖形的走訪可以判斷圖形是否連通, 並找出連通單元及路徑. 圖形走訪的方法有兩種 : "先深後廣走訪" 及 "先廣後深走訪". 

先深後廣法 : 
先深後廣走訪的方式有點類似前序走訪. 是從圖形的某一頂點開始走訪, 被拜訪過的頂點就作上已拜訪的記號, 接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任意一個頂點, 並做上已拜訪的記號, 再以該點為新的起點繼續進行先深後廣的搜尋. 
這種圖形追蹤方法結合了遞迴與堆疊兩種資料結構的技巧, 由於不小心會造成無窮迴路, 所以必須加上一個變數, 判斷該節點是否已經走訪完畢. 
底下我們以下圖來看看這個方法的走訪過程 : 
 
步驟一 : 以頂點1 為起點, 將相鄰的頂點2及頂點5放入堆疊. (頂點1已拜訪
 
步驟二 : 取出頂點2, 將頂點2相鄰且未拜訪過的頂點3及頂點4放入堆疊. (頂點1,2 已拜訪
 
步驟三 : 取出頂點3, 將與頂點3相鄰且未拜訪過的頂點4 及頂點5放進堆疊. (頂點1,2,3 已拜訪
 
步驟四 : 取出頂點4, 將與頂點4相鄰且未拜訪過的頂點5放入堆疊. (頂點1,2,3,4 已拜訪
 
步驟五 : 取出頂點5, 將與頂點5相鄰且未拜訪過的頂點放入堆疊, 這裡與頂點5相鄰的頂點已經都拜訪過, 所以無須再放入堆疊. (頂點1,2,3,4,5 已拜訪) 
 
步驟六 : 將堆疊內的值取出並判斷是否已經走訪過, 直到堆疊內無節點可走訪為止. 故先深後廣的走訪順序為 : 頂點1, 頂點2, 頂點3, 頂點4, 頂點5. 

範例代碼 : 
  1. #include   
  2.   
  3. using namespace std;  
  4.   
  5. class graphicPoint{  
  6. public:  
  7.     int val;  
  8.     class graphicPoint *next;  
  9.     graphicPoint(){  
  10.         next = NULL;  
  11.         val = -1;  
  12.     }  
  13. };  
  14.   
  15. int run[6] = {0};  
  16. class graphicPoint head[6]; // 共有5個頂點  
  17. void dfs(int current) {  
  18.     graphicPoint *ptr;  
  19.     run[current] = 1;  
  20.     cout << "[" << current << "] ";  
  21.     ptr = head[current].next;  
  22.     while(ptr!=NULL) {  
  23.         if(run[ptr->val]==0)  
  24.             dfs(ptr->val);  
  25.         ptr = ptr->next;  
  26.     }  
  27. }  
  28. void main(bool b) {  
  29.     if(b) {       
  30.         int data[14][2] = {{1,2}, {2,1}, {1,5}, {5,1}, {2,3}, {3,2}, {2,4}, {4,2}, {3,4}, {4,3}, {3,5}, {5,3}, {4,5}, {5,4}}; //圖形邊線陣列宣告  
  31.         for(int i=0; i<14; i++) {  
  32.             int tmpi = data[i][0];  
  33.             int tmpj = data[i][1];  
  34.             graphicPoint *npt = new graphicPoint;  
  35.             npt->val = tmpj;  
  36.             graphicPoint *pt = &head[tmpi];  
  37.             while(pt->next != NULL)  
  38.                 pt = pt->next;  
  39.             pt->next = npt;            
  40.         }  
  41.         cout << "圖形鄰接串列內容 : " << endl;  
  42.         for(int i=1; i<6; i++) {  
  43.             graphicPoint *pt = head[i].next;  
  44.             cout << "頂點 " << i << "=>";  
  45.             while(pt!=NULL)  {  
  46.                 cout << "[" << pt->val << "] ";  
  47.                 pt  = pt->next;  
  48.             }  
  49.             cout << endl;  
  50.         }  
  51.         cout << "深度優先走訪頂點 :" << endl;  
  52.         for(int i=0; i<6; i++) { // 初始化run 陣列  
  53.             run[i] = 0;  
  54.         }  
  55.         dfs(1);  // 以頂點1為起點  
  56.         printf("\n");  
  57.     }  
  58. }  
執行結果 : 
圖形鄰接串列內容 :
頂點 1=>[2] [5]
頂點 2=>[1] [3] [4]
頂點 3=>[2] [4] [5]
頂點 4=>[2] [3] [5]
頂點 5=>[1] [3] [4]
深度優先走訪頂點 :
[1] [2] [3] [4] [5]

補充說明 : 
[ 資料結構 小學堂 ] 圖形結構 : 圖形表示法

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!