程式扎記: [ Java 代碼範本 ] JGraphT - Bread First Search

標籤

2015年10月31日 星期六

[ 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: 
  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) 
[ 資料結構 小學堂 ] 佇列 : 認識佇列

沒有留言:

張貼留言

網誌存檔

關於我自己

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