fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.Stack;
  6.  
  7. /**
  8.  * DFS traversal in a undirected Graph using Stack
  9.  * @author Prateek
  10.  *
  11.  */
  12. class DFSIterative {
  13.  
  14. 	private int numVertices;
  15. 	private int numEdges;
  16.  
  17. 	// Map to maintain adjacency List
  18. 	private Map<Integer, ArrayList<Integer>> adjList;
  19. 	// Map to maintain visit status
  20. 	private Map<Integer, Boolean> vistedStatus;
  21.  
  22. 	/*
  23. 	 * Constructor when number of vertices are not known
  24. 	 */
  25. 	public DFSIterative() {
  26. 		this.adjList = new HashMap<Integer, ArrayList<Integer>>();
  27. 		this.vistedStatus = new HashMap<Integer, Boolean>();
  28. 	}
  29.  
  30. 	/*
  31. 	 * Constructor when number of vertices are known
  32. 	 */
  33. 	public DFSIterative(int V) {
  34. 		this.numVertices = V;
  35. 		this.adjList = new HashMap<Integer, ArrayList<Integer>>(V);
  36. 		this.vistedStatus = new HashMap<Integer, Boolean>(V);
  37. 	}
  38.  
  39. 	/**
  40. 	 * Edge in a un-directed graph
  41. 	 */
  42. 	private void addEdge(int src, int dest) {
  43.  
  44. 		/* Forward Edge */
  45. 		ArrayList<Integer> list = adjList.get(src);
  46. 		if (list == null)
  47. 			list = new ArrayList<Integer>();
  48.  
  49. 		list.add(dest);
  50. 		adjList.put(src, list);
  51. 		vistedStatus.put(src, false); // visit status set to false
  52.  
  53. 		/* Reverse Edge */
  54. 		list = adjList.get(dest);
  55. 		if (list == null)
  56. 			list = new ArrayList<Integer>();
  57.  
  58. 		list.add(src);
  59. 		adjList.put(dest, list);
  60. 		vistedStatus.put(dest, false); // visit status set to false
  61.  
  62. 	}
  63.  
  64. 	/**
  65. 	 * Procedure for Iterative DFS using Stack
  66. 	 */
  67. 	public void dfsIterative(int startNode) {
  68. 		System.out.println("Iterative DFS : ");
  69. 		Stack<Integer> stack = new Stack<Integer>();
  70.  
  71. 		stack.push(startNode);
  72. 		vistedStatus.put(startNode, true);
  73.  
  74. 		while (!stack.empty()) {
  75.  
  76. 			int item = stack.pop();
  77.  
  78. 			System.out.println("Poped Item : " + item);
  79.  
  80. 			List<Integer> list = adjList.get(item);
  81. 			int size = list.size();
  82.  
  83. 			for (int j = 0; j < size; j++) {
  84. 				int dest = list.get(j);
  85.  
  86. 				if (!vistedStatus.get(dest)) {
  87. 					vistedStatus.put(dest, true);
  88. 					stack.push(dest);
  89. 				}
  90. 			}
  91. 		}
  92. 	}
  93.  
  94. 	public static void main(String[] args) {
  95. 		DFSIterative g = new DFSIterative(6);
  96.  
  97. 		g.addEdge(0, 1);
  98. 		g.addEdge(0, 2);
  99. 		g.addEdge(1, 2);
  100. 		g.addEdge(2, 3);
  101. 		g.addEdge(1, 3);
  102.  
  103. 		g.dfsIterative(0);
  104.  
  105. 	}
  106. }
  107.  
Success #stdin #stdout 0.07s 381184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Iterative DFS : 
Poped Item : 0
Poped Item : 2
Poped Item : 3
Poped Item : 1
https://ideone.com/Yjm6zB
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!