fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Map.Entry;
  7. import java.util.Set;
  8.  
  9. /**
  10.  * BFS in a Undirected Graph, Connected Graph
  11.  * @author Prateek
  12.  */
  13. class DFS {
  14.  
  15. 	private int numVertices;
  16. 	private int numEdges;
  17.  
  18. 	//Map to maintain adjacency List
  19. 	private Map<Integer,ArrayList<Integer>> adjList;
  20. 	// Map to maintain visit status
  21. 	private Map<Integer, Boolean> vistedStatus;
  22.  
  23. 	/*
  24. 	 * Constructor when number of vertices are not known
  25. 	 */
  26. 	public DFS() {
  27. 		this.adjList = new HashMap<Integer,ArrayList<Integer>>();
  28. 		this.vistedStatus = new HashMap<Integer, Boolean>() ; 
  29. 	}
  30.  
  31. 	/*
  32. 	 * Constructor when number of vertices are known
  33. 	 */
  34. 	public DFS(int V) {
  35. 		this.numVertices = V;
  36. 		this.adjList = new HashMap<Integer,ArrayList<Integer>>(V);
  37. 		this.vistedStatus = new HashMap<Integer, Boolean>(V) ; 
  38. 	}
  39.  
  40.    /**
  41.     * Edge in a un-directed graph
  42.     */
  43. 	private void addEdge(int src, int dest) {
  44.  
  45. 		/*Forward Edge */
  46. 		ArrayList<Integer> list=adjList.get(src);			
  47. 		if(list==null)
  48. 			list=new ArrayList<Integer>();
  49.  
  50. 		list.add(dest);
  51. 		adjList.put(src,list);	
  52. 		vistedStatus.put(src, false);  //visit status set to false
  53.  
  54. 		/* Reverse Edge */
  55. 		list=adjList.get(dest);			
  56. 		if(list==null)
  57. 			list=new ArrayList<Integer>();
  58.  
  59. 		list.add(src);
  60. 		adjList.put(dest,list);	
  61. 		vistedStatus.put(dest, false);  //visit status set to false
  62.  
  63. 	}
  64.  
  65. 	/**
  66. 	 * Procedure for Recursive DFS
  67. 	 */
  68. 	public void dfs(){
  69.  
  70. 		System.out.println("Recursive DFS :");
  71. 		Set<Map.Entry<Integer, Boolean>> entrys = vistedStatus.entrySet();
  72.  
  73. 		Iterator<Entry<Integer, Boolean>> it = entrys.iterator();
  74.  
  75. 		while(it.hasNext())
  76. 		{
  77. 			Map.Entry<Integer, Boolean> entry = it.next();
  78. 			boolean isVisited=entry.getValue();
  79. 			if(!isVisited){
  80. 				dfsUtil(entry.getKey());	
  81. 			}
  82. 		}
  83. 	}
  84.  
  85. 	public void dfsUtil(int vertex){
  86. 		List <Integer> list = adjList.get(vertex) ;
  87.  
  88. 		vistedStatus.put(vertex, true) ;
  89. 		System.out.println(vertex + "\t");
  90. 		int size = list.size();
  91. 		for(int i = 0;i < size ; i++){
  92. 			int v=list.get(i);
  93.  
  94. 			if(!vistedStatus.get(v))
  95. 				dfsUtil(v);
  96. 		}
  97. 	}
  98.  
  99. 	public static void main(String[] args) {
  100. 		DFS g=new DFS(6);
  101.  
  102. 		g.addEdge(0, 1);
  103. 		g.addEdge(0, 2);
  104. 		g.addEdge(1, 2);
  105. 		g.addEdge(2, 3);
  106. 		g.addEdge(1, 3);
  107.  
  108. 		g.dfs();
  109.  
  110. 	}
  111. }
  112.  
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Recursive DFS :
0	
1	
2	
3
https://ideone.com/ZGsVsW
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!