程式扎記: [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 - 先廣後深法

標籤

2010年10月25日 星期一

[ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 - 先廣後深法

先廣後深法 : 
之前談到的先深後廣法是利用堆疊及遞迴的技巧來走訪圖形, 而先廣後深法 (Breadth-First Search, bfs) 走訪方式則是以佇列及遞迴技巧來走訪, 也是從圖形某一頂點開始走訪, 被拜訪過的頂點就做上已拜訪的記號. 接著走訪此頂點的所有相鄰且未拜訪過的頂點中的任一個頂點, 並且做上已拜訪的記號, 再以該頂點做為新的起點繼續進行先廣後深的搜尋. 底下我們以下圖來看看 BFS 的走訪過程 : 
 

步驟一 : 以頂點一為起點, 與頂點一相鄰且未拜訪過的頂點2 及頂點 5放入佇列 : 
 

步驟二 : 取出頂點2, 將與頂點2 相鄰且未拜訪過的頂點3 及頂點4 放入佇列 : 
 

步驟三 : 取出頂點5, 將與頂點5 相鄰且未拜訪過的頂點3 及頂點4 放入佇列 : 
 

步驟四 : 取出頂點3, 將與頂點3 相鄰且未拜訪過的頂點4 放入佇列 : 
 

步驟五 : 取出頂點4, 將與頂點4 相鄰且未拜訪過的頂點放入佇列中, 各位可以發現與頂點4 相鄰的頂點全部都被拜訪過, 所以無須再放入佇列中. 
 

步驟六 : 將佇列值取出並判斷是否已經走訪過, 直到佇列內無節點可走訪為止. 所以先廣後深走訪順序為 : 頂點1 > 頂點2 > 頂點5 > 頂點3 > 頂點4 

範例代碼 : 
  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. int run[6] = {0};  
  15. class graphicPoint head[6]; // 共有5個頂點  
  16.   
  17. #define MAX_QUEUESIZE 10 // 定義佇列最大容量  
  18. int front = -1;  
  19. int rear = -1;  
  20. int queue[MAX_QUEUESIZE] = {0};  
  21. void enqueue(int val) {  
  22.     if(rear >= MAX_QUEUESIZE)  
  23.         return;  
  24.     rear++;  
  25.     queue[rear] = val;  
  26. }  
  27.   
  28. int dequeue(){  
  29.     if(front == rear) return -1;  
  30.     front++;  
  31.     return queue[front];  
  32. }  
  33.   
  34. void bfs(int current) { //先廣後深法  
  35.     graphicPoint *tmpnode;  
  36.     enqueue(current); // 將第一個頂點存入佇列       
  37.     while(front != rear) { // 判斷目前是否為空佇列  
  38.         current=dequeue(); // 將頂點從佇列取出  
  39.         if(run[current]==0) {  
  40.             run[current] = 1// 將走訪過的頂點設為1  
  41.             cout << "[" << current << "] ";  
  42.         }  
  43.         tmpnode = head[current].next;  
  44.         while(tmpnode!=NULL) {  
  45.             if(run[tmpnode->val]==0)  
  46.                 enqueue(tmpnode->val);  
  47.             tmpnode = tmpnode->next;  
  48.         }  
  49.     }  
  50. }  
  51.   
  52. void ch07_05(bool b) {  
  53.     if(b) {  
  54.         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}}; //圖形邊線陣列宣告  
  55.         for(int i=0; i<14; i++) {  
  56.             int tmpi = data[i][0];  
  57.             int tmpj = data[i][1];  
  58.             graphicPoint *npt = new graphicPoint;  
  59.             npt->val = tmpj;  
  60.             graphicPoint *pt = &head[tmpi];  
  61.             while(pt->next != NULL)  
  62.                 pt = pt->next;  
  63.             pt->next = npt;            
  64.         }  
  65.         cout << "圖形鄰接串列內容 : " << endl;  
  66.         for(int i=1; i<6; i++) {  
  67.             graphicPoint *pt = head[i].next;  
  68.             cout << "頂點 " << i << "=>";  
  69.             while(pt!=NULL)  {  
  70.                 cout << "[" << pt->val << "] ";  
  71.                 pt  = pt->next;  
  72.             }  
  73.             cout << endl;  
  74.         }  
  75.         cout << "廣度優先走訪頂點 :" << endl;  
  76.         for(int i=0; i<6; i++) { // 初始化run 陣列  
  77.             run[i] = 0;  
  78.         }  
  79.         bfs(1);  
  80.         printf("\n");  
  81.     }  
  82. }  
執行結果 : 
圖形鄰接串列內容 :
頂點 1=>[2] [5]
頂點 2=>[1] [3] [4]
頂點 3=>[2] [4] [5]
頂點 4=>[2] [3] [5]
頂點 5=>[1] [3] [4]
廣度優先走訪頂點 :
[1] [2] [5] [3] [4]

補充說明 : 
[ 資料結構 小學堂 ] 佇列 : 認識佇列

沒有留言:

張貼留言

網誌存檔

關於我自己

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