fork(2) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.Map;
  7. import java.util.Map.Entry;
  8. import java.util.Queue;
  9. import java.util.Set;
  10. import java.util.Stack;
  11.  
  12. /**
  13.  * BFS in a Undirected Graph, Connected Graph
  14.  * @author Prateek
  15.  */
  16. class UndirectedGraphAPI {
  17.  
  18. 	private int numVertices;
  19. 	private int numEdges;
  20.  
  21. 	//Map to maintain adjacency List
  22. 	private Map<Integer,ArrayList<Integer>> adjList;
  23. 	// Map to maintain visit status
  24. 	private Map<Integer, Boolean> vistedStatus;
  25.  
  26. 	/*
  27. 	 * Constructor when number of vertices are not known
  28. 	 */
  29. 	public UndirectedGraphAPI() {
  30. 		this.adjList = new HashMap<Integer,ArrayList<Integer>>();
  31. 		this.vistedStatus = new HashMap<Integer, Boolean>() ; 
  32. 	}
  33.  
  34. 	/*
  35. 	 * Constructor when number of vertices are known
  36. 	 */
  37. 	public UndirectedGraphAPI(int V) {
  38. 		this.numVertices = V;
  39. 		this.adjList = new HashMap<Integer,ArrayList<Integer>>(V);
  40. 		this.vistedStatus = new HashMap<Integer, Boolean>(V) ; 
  41. 	}
  42.  
  43.    /**
  44.     * Edge in a un-directed graph
  45.     */
  46. 	protected void addEdge(int src, int dest) {
  47.  
  48. 		/*Forward Edge */
  49. 		ArrayList<Integer> list=adjList.get(src);			
  50. 		if(list==null)
  51. 			list=new ArrayList<Integer>();
  52.  
  53. 		list.add(dest);
  54. 		adjList.put(src,list);	
  55. 		vistedStatus.put(src, false);  //visit status set to false
  56.  
  57. 		/* Reverse Edge */
  58. 		list=adjList.get(dest);			
  59. 		if(list==null)
  60. 			list=new ArrayList<Integer>();
  61.  
  62. 		list.add(src);
  63. 		adjList.put(dest,list);	
  64. 		vistedStatus.put(dest, false);  //visit status set to false
  65. 	}
  66.  
  67. 	/**
  68. 	 * Procedure for Recursive DFS
  69. 	 */
  70. 	public void dfs(){
  71.  
  72. 		System.out.println("Recursive DFS :");
  73. 		Set<Map.Entry<Integer, Boolean>> entrys = vistedStatus.entrySet();
  74.  
  75. 		Iterator<Entry<Integer, Boolean>> it = entrys.iterator();
  76.  
  77. 		while(it.hasNext())
  78. 		{
  79. 			Map.Entry<Integer, Boolean> entry = it.next();
  80. 			boolean isVisited=entry.getValue();
  81. 			if(!isVisited){
  82. 				dfsUtil(entry.getKey());	
  83. 			}
  84. 		}
  85. 	}
  86.  
  87. 	public void dfsUtil(int vertex){
  88. 		List <Integer> list = adjList.get(vertex) ;
  89.  
  90. 		vistedStatus.put(vertex, true) ;
  91. 		System.out.println(vertex + "\t");
  92. 		int size = list.size();
  93. 		for(int i = 0;i < size ; i++){
  94. 			int v=list.get(i);
  95. 			if(!vistedStatus.get(v))
  96. 				dfsUtil(v);
  97. 		}
  98. 	}
  99.  
  100.  
  101. 	//	procedure DFS(Graph,source):
  102. 	//	      create a stack S
  103. 	//	      push source onto S
  104. 	//	      mark source
  105. 	//	      while S is not empty:
  106. 	//	          pop an item from S into v
  107. 	//	          for each edge e incident on v in Graph:
  108. 	//	              let w be the other end of e
  109. 	//	              if w is not marked:
  110. 	//	                 mark w
  111. 	//	                 push w onto S
  112.  
  113.  
  114. 	/**
  115. 	 * Procedure for Iterative DFS using Stack
  116. 	 */
  117. 	public void dfsIterative(int startNode){
  118. 		System.out.println("Iterative DFS : ");
  119. 		Stack<Integer> stack = new Stack<Integer>();
  120.  
  121. 				stack.push(startNode);
  122. 				vistedStatus.put(startNode, true);
  123.  
  124. 				while(!stack.empty()){
  125.  
  126. 					int item=stack.pop();
  127.  
  128. 					System.out.println("Poped Item : "+ item);
  129.  
  130. 					List<Integer> list = adjList.get(item);
  131. 					int size= list.size();
  132.  
  133. 					for(int j=0; j<size ;j++){
  134. 						int dest=list.get(j);
  135.  
  136. 						if(!vistedStatus.get(dest)){
  137. 							vistedStatus.put(dest, true);
  138. 							stack.push(dest);
  139. 						}
  140. 					}
  141. 				}
  142. 	}
  143.  
  144.  
  145.  
  146. 	/////======== BREADTH FIRST SEARCH  ========/////////
  147. 	/**
  148. 	 * Desc: Breadth First Search: using queue to visit to all nodes in a connected graph  
  149. 	 */
  150. 	public void bfs(int startNode)
  151. 	{
  152. 		Queue<Integer> bfsQueue = new LinkedList<Integer>();
  153.  
  154. 		// stating node visit status set to true
  155. 		vistedStatus.put(startNode, true);
  156.  
  157. 		// start node added to Queue
  158. 		bfsQueue.add(startNode);
  159.  
  160. 		while(!bfsQueue.isEmpty())
  161. 		{
  162. 			// Node poped from Queue
  163. 			int node=bfsQueue.poll();
  164. 			System.out.println("Node poped is : "+node);
  165.  
  166. 			// all connected node list of a give node
  167. 			List<Integer> list=adjList.get(node);
  168.  
  169. 			int size=list.size();
  170. 			System.out.print("Connected Nodes are : ");
  171. 			for(int i=0;i <size; ++i)
  172. 			{
  173. 				int adjNode=list.get(i);
  174. 				System.out.print(adjNode +"   ");
  175. 				boolean isVisited=vistedStatus.get(adjNode);
  176. 				if(!isVisited)
  177. 				{
  178. 					vistedStatus.put(adjNode, true);
  179. 					bfsQueue.add(adjNode);
  180. 				}
  181. 			}
  182. 			System.out.println("\n===================");
  183. 		}
  184. 	}
  185.  
  186. 	public List<Integer> adj(int vertex){
  187. 		return adjList.get(vertex);
  188. 	}
  189.  
  190. 	public static void main(String[] args) {
  191. 		UndirectedGraphAPI g=new UndirectedGraphAPI(4);
  192.  
  193. 		// use for bfs and dfs
  194. 		g.addEdge(0, 1);
  195. 		g.addEdge(0, 2);
  196. 		g.addEdge(1, 2);
  197. 		g.addEdge(2, 3);
  198. 		g.addEdge(1, 3);
  199.  
  200. 		//g.bfs(0);
  201. 		//g.dfsIterative(0);
  202. 		g.dfs();
  203.  
  204. 	}
  205. }
  206.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Recursive DFS :
0	
1	
2	
3
https://ideone.com/aF5PRk
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!