程式扎記: [ Java 代碼範本 ] JGraphT - How to use the DepthFirstSearchIterator class to run a depth first search

標籤

2015年10月31日 星期六

[ Java 代碼範本 ] JGraphT - How to use the DepthFirstSearchIterator class to run a depth first search

Source From Here 
Question 
I am experimenting with JGraphT and have hit a brick wall trying to implement a depth first search using the JGraphT API. I have created a simple graph with nodes and vertices's as follows: 
  1. DirectedGraph graph = new   
  2.     DefaultDirectedGraph (DefaultEdge.class);  
  3.   
  4. graph.addVertex(7);  
  5. graph.addVertex(4);  
  6. graph.addVertex(9);  
  7. graph.addVertex(3);  
  8. graph.addVertex(2);  
  9. graph.addVertex(5);  
  10.   
  11.   
  12. graph.addEdge(74);  
  13. graph.addEdge(79);  
  14. graph.addEdge(93);  
  15. graph.addEdge(32);  
  16. graph.addEdge(35);  
How would I use the DepthFirstIterator to run DFS on this graph? 

How-To 
Just traverse the graph using DepthFirstIterator. Here is an example: 
  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.DepthFirstIterator  
  9. import org.jgrapht.traverse.GraphIterator  
  10.   
  11. UndirectedGraph graph =  
  12.         new SimpleGraph (DefaultEdge.class);  
  13.   
  14.           
  15. // Graph          
  16. // 0-----1  
  17. //   |  
  18. //   +---2  
  19. //   |  
  20. //   +-------6---+  
  21. //   |           |  
  22. //   |   +---3   |  
  23. //   +---5   +   |  
  24. //       +---4---+                                                                    
  25. 7.times{  
  26.     graph.addVertex(it);  
  27. }                 
  28.   
  29. def edges = [:]  
  30. edges[0]=[1,2,5,6]  
  31. edges[3]=[4,5]  
  32. edges[4]=[6,5]  
  33.   
  34. edges.each{ k, v->     
  35.     v.each{  
  36.         graph.addEdge(k, it)  
  37.     }  
  38. }  
  39.   
  40. GraphIterator iterator =  
  41.         new DepthFirstIterator(graph, 0);  
  42. while (iterator.hasNext()) {  
  43.     System.out.printf("%d ", iterator.next());  
  44. }  
  45. println()  
For more control, you can attach TraversalListener to the iterator using addTraversalListener(). Here is an example of a basic listener. 

Supplement 
Coursera - Algorithms, Part II - Depth First Search 
[ DS & Algorithm in C++ ] Section 9.6 : Applications of Depth-First Search 
[ Algorithm ] Maze problem - Using Online DFS Search 
[ Intro Alg ] Elementary Graph Algorithms - Depth-first search

沒有留言:

張貼留言

網誌存檔

關於我自己

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