[ Java 代碼範本 ] JGraphT - Bread First Search

Introduction 
先廣後深法 - BFS (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 

Sample Code 
底下範例代碼使用 JGrapthT 中的 BreadthFirstIterator 進行 BFS 訪問 Graph 的每個 Vertex: 

view plaincopy to clipboardprint?

1. package lab;  
2.   
3. import static org.junit.Assert.*  
4.   
5. import org.jgraph.graph.DefaultEdge  
6. import org.jgrapht.UndirectedGraph  
7. import org.jgrapht.graph.SimpleGraph  
8. import org.jgrapht.traverse.BreadthFirstIterator  
9. import org.jgrapht.traverse.DepthFirstIterator  
10. import org.jgrapht.traverse.GraphIterator  
11.   
12. UndirectedGraph graph =  
13.         new SimpleGraph (DefaultEdge.class);  
14.   
15.           
16. // Graph          
17. // 1-----2-------+  
18. //   |           |             
19. //   +---5---3---+---4  
20. //       |           |  
21. //       +-----------+  
22.                                                                               
23. 5.times{  
24.     graph.addVertex(it+1);  
25. }                 
26.   
27. def edges = [:]  
28. edges[1]=[2,5]  
29. edges[2]=[3,4]  
30. edges[3]=[5,4]  
31. edges[4]=[5]  
32.   
33. edges.each{ k, v->     
34.     v.each{  
35.         graph.addEdge(k, it)  
36.     }  
37. }  
38.   
39. iterator =  
40.     new BreadthFirstIterator(graph, 1);  
41. while (iterator.hasNext()) {  
42. System.out.printf("%d ", iterator.next());  
43. }  
44. println()  

執行結果: 

1 2 5 3 4

Supplement 
* JGraphT - Depth First Search 
* Coursera - Algorithms, Part II - Breadth First Search 
* [ Intro Alg ] Elementary Graph Algorithms - Breadth-first search 
* [ 資料結構 小學堂 ] 圖形結構 : 圖形的追蹤 - 先廣後深法 (BFS) 
* [ 資料結構 小學堂 ] 佇列 : 認識佇列