fork(6) download
copy 
  1. //package gfgGraphs;
  2.  
  3. import java.util.*;
  4. // this is a directed graph
  5. // if you want undirected graph, add edges from v1->v2 && v2->v1
  6. // use hashmap to construct adjacency list graph in java
  7.  class Graph {
  8.  
  9. 	HashMap<Integer, LinkedList<Integer>> adj; // adjacency hashmap
  10. 	HashMap<Integer,Boolean> visited; 
  11.  
  12. 	// constructor to construct a graph from the nodes
  13. 	 public  Graph(int[] nodes){
  14. 		 adj = new HashMap<Integer,LinkedList<Integer>>();
  15. 		 visited = new HashMap<Integer,Boolean>();
  16.  
  17.  
  18. 		for(int i=0;i<nodes.length;i++){
  19. 			adj.put(nodes[i], new LinkedList<Integer>());
  20. 			visited.put(nodes[i], false);
  21. 		}
  22. 	}
  23. 	 // add edge from vertices v1 to v2
  24. 	 void addEdge(int v1,int v2){
  25. 		 adj.get(v1).add(v2);
  26. 	 }
  27.  
  28. 	 // get neighbors of a vertex
  29. 	 LinkedList<Integer> getNeighbors(int v){
  30. 		 return adj.get(v);
  31. 	 }
  32. 	// Breadth First Traversal of the Graph (Directed)
  33. 	// runtime: O(V+E) , no of vertices + edges
  34. 	 static void BFS(Graph g,int n){
  35. 		 Queue<Integer> q = new LinkedList<Integer>();
  36. 		 q.add(n);
  37.  
  38. 		while(!q.isEmpty()){
  39. 			n = q.peek();
  40. 			System.out.print(n+" ");
  41. 			g.visited.put(n, true);
  42.  
  43. 			Iterator<Integer> i = g.adj.get(q.peek()).iterator(); // peek() returns the head of the queue without removing
  44. 			q.poll(); // poll() removes and returns the head of the queue
  45. 			while(i.hasNext() ){
  46. 				Integer l = i.next();
  47. 				if(!g.visited.get(l)){					
  48. 					g.visited.put(l, true);
  49. 					q.add(l);				
  50. 				}
  51. 			}
  52. 		}
  53.  
  54. 	 }
  55. 	 // runtime: O(V+E) , no of vertices + edges
  56. 	 static void DFS(Graph g, int n){
  57. 		 if(!g.visited.get(n)){
  58. 			 System.out.print(n+" ");
  59. 			 g.visited.put(n, true);
  60. 			 Iterator<Integer> i = g.adj.get(n).iterator();
  61. 			 while(i.hasNext()){
  62. 				 Integer l = i.next();
  63. 				 DFS(g,l);
  64. 			 }
  65. 		 }
  66. 	 }
  67.  
  68. 	 // returns true even if one cycle is present
  69. 	 // run time: O(V), where V-no of vertices
  70. 	 static boolean isCyclic(Graph g,int n){
  71. 		 if(g.visited.get(n))
  72. 			 return true;
  73. 		 g.visited.put(n, true);
  74. 		 Integer k = null;
  75. 		 // try statement to return false if 
  76. 		 // k throws an exception:No such element exists
  77. 		 try{
  78. 		  k = g.adj.get(n).element();
  79. 		 }
  80. 		 catch(Exception e){
  81. 			 return false;
  82. 		 }
  83. 		 return isCyclic(g, k);
  84.  
  85. 	 }
  86.  
  87.  
  88. 	 /* comments from geeksforgeeks
  89. 	 Nice approach but there is a problem. I don't think isCyclic method works here. 
  90. 	 You need to have a cycleDetectionMap just like visited map. Initialize cycleDetectionMap to false 
  91. 	 in the constructor. Your isCyclic method should look something like below.
  92.  
  93. 	boolean cyclesInGraph(Integer root){
  94. 	if (!(visitedMap.get(root))) {
  95. 	visitedMap.put(root, true);
  96. 	cycleDetectionMap.put(root, true);
  97. 	List<integer> adjacencyList = adjacencyMap.get(root);
  98. 	for(int i = 0; i < adjacencyList.size(); i++) {
  99. 	int current = adjacencyList.get(i);
  100. 	if(cyclesInGraph(current)){
  101. 	return true;
  102. 	} else if (cycleDetectionMap.get(current)) {
  103. 	return true;
  104. 	}
  105. 	}
  106. 	cycleDetectionMap.put(root, false);
  107. 	}
  108. 	return false;
  109. 	}
  110.  
  111. Also how about having a reset method in graph to clear visited and cycleDetection maps?
  112.  
  113. 	 */
  114.  
  115. 	public static void main(String[] args) {
  116. 		// TODO Auto-generated method stub
  117. 		int ar[] = {10,41,62,83};
  118. 		int ar2[] = {1,2,3,4,5,6,7};
  119. 		int ar3[] = {1,2,3,4,5,6,7,8,9,10,11,12};
  120. 		Graph g = new Graph(ar); // BFS graph
  121. 		Graph g2 = new Graph(ar); // DFS graph
  122. 		Graph g3 = new Graph(ar);
  123. 		Graph g4 = new Graph(ar3);
  124.  
  125. 		g.addEdge(10, 41);
  126. 	    g.addEdge(10, 62);
  127. 	    g.addEdge(41, 62);
  128. 	    g.addEdge(62, 10);
  129. 	    g.addEdge(62, 41);
  130. 	    g.addEdge(62, 83);
  131. 	    g.addEdge(83, 83);
  132.  
  133. 	   // System.out.println("BFS Neighbors"+g.getNeighbors(10));
  134. 	    System.out.print("BFS: ");
  135. 	    BFS(g,10);
  136. 	    System.out.println();
  137.  
  138. 	    // Depth first traversal
  139.  
  140.  
  141. 	    g2.addEdge(10, 41);
  142. 	    g2.addEdge(10, 62);
  143. 	    g2.addEdge(41, 62);
  144. 	 //   g2.addEdge(62, 41);
  145. 	    g2.addEdge(62, 10);
  146.  
  147. 	    g2.addEdge(62, 83);
  148. 	//    g2.addEdge(83, 83);
  149. 	  //  g2.addEdge(83, 41);
  150.  
  151. 	    System.out.print("DFS: ");
  152. 	    DFS(g2,62);
  153. 	    System.out.println();
  154.  
  155.  
  156. 	    // Cyclic graph
  157. 	    g3.addEdge(10, 41);
  158. 	    g3.addEdge(41, 62);
  159. 	   // g3.addEdge(62, 83);
  160. 	    g3.addEdge( 62,10);
  161. 	    //g3.addEdge(83,10);
  162.  
  163. 	    boolean b = isCyclic(g3,10);
  164. 	    if(b)
  165. 	    	System.out.println("The graph is cyclic");
  166. 	    else
  167. 	    	System.out.println("Not a cyclic graph");
  168.  
  169. 	    g4.addEdge(1,2);
  170. 	    g4.addEdge(1,3);
  171. 	    g4.addEdge(1,4);
  172. 	    g4.addEdge(2,5);
  173. 	    g4.addEdge(2,6);
  174. 	    g4.addEdge(5,9);
  175. 	    g4.addEdge(5,10);
  176. 	    g4.addEdge(4,7);
  177. 	    g4.addEdge(4,8);
  178. 	    g4.addEdge(7,11);
  179. 	    g4.addEdge(7,12);
  180. 	    System.out.print("BFS: ");
  181. 	    BFS(g4,1);
  182. 	    System.out.println();
  183.  
  184.  
  185. 	    Graph g5 = new Graph(ar3);
  186.  
  187. 	    g5.addEdge(1,2);
  188. 	    g5.addEdge(1,7);
  189. 	    g5.addEdge(1,8);
  190. 	    g5.addEdge(2,3);
  191. 	    g5.addEdge(2,6);
  192. 	    g5.addEdge(3,4);
  193. 	    g5.addEdge(3,5);
  194. 	    g5.addEdge(8,9);
  195. 	    g5.addEdge(8,12);
  196. 	    g5.addEdge(9,10);
  197. 	    g5.addEdge(9,11);
  198. 	    System.out.print("DFS: ");
  199. 	    DFS(g5,1);
  200. 	    System.out.println();
  201.  
  202. 	}
  203.  
  204. }
  205.  
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
BFS: 10 41 62 83 
DFS: 62 10 41 83 
The graph is cyclic
BFS: 1 2 3 4 5 6 7 8 9 10 11 12 
DFS: 1 2 3 4 5 6 7 8 9 10 11 12
https://ideone.com/U3pGNE
Graph:Directed(adjacency list) , BFS , DFS, isCyclic
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

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!