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

先廣後深法 : 
之前談到的先深後廣法是利用堆疊及遞迴的技巧來走訪圖形, 而先廣後深法 (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 

範例代碼 : 

view plaincopy to clipboardprint?

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]

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