fork download
copy 
  1.  
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.Map;
  7. import java.util.Queue;
  8.  
  9. /**
  10.  * BFS in a Undirected BFS, Connected BFS
  11.  * @author Prateek
  12.  */
  13.  class BFS {
  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 BFS() {
  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 BFS(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 BFS
  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. 	/////======== BREADTH FIRST SEARCH  ========/////////
  66. 	/**
  67. 	 * Desc: Breadth First Search: using queue to visit to all nodes in a connected BFS  
  68. 	 */
  69. 	public void bfs(int startNode)
  70. 	{
  71. 		Queue<Integer> bfsQueue = new LinkedList<Integer>();
  72.  
  73. 		// stating node visit status set to true
  74. 		vistedStatus.put(startNode, true);
  75.  
  76. 		// start node added to Queue
  77. 		bfsQueue.add(startNode);
  78.  
  79. 		while(!bfsQueue.isEmpty())
  80. 		{
  81. 			// Node poped from Queue
  82. 			int node=bfsQueue.poll();
  83. 			System.out.println("Node poped is : "+node);
  84.  
  85. 			// all connected node list of a give node
  86. 			List<Integer> list=adjList.get(node);
  87.  
  88. 			int size=list.size();
  89. 			System.out.print("Connected Nodes are : ");
  90. 			for(int i=0;i <size; ++i)
  91. 			{
  92. 				int adjNode=list.get(i);
  93. 				System.out.print(adjNode +"   ");
  94. 				boolean isVisited=vistedStatus.get(adjNode);
  95. 				if(!isVisited)
  96. 				{
  97. 					vistedStatus.put(adjNode, true);
  98. 					bfsQueue.add(adjNode);
  99. 				}
  100. 			}
  101. 			System.out.println("\n===================");
  102. 		}
  103. 	}
  104.  
  105. 	public static void main(String[] args) {
  106. 		BFS g=new BFS(6);
  107.  
  108. 		// use for bfs and dfs
  109. 		g.addEdge(0, 1);
  110. 		g.addEdge(0, 2);
  111. 		g.addEdge(1, 2);
  112. 		g.addEdge(2, 3);
  113. 		g.addEdge(1, 3);
  114.  
  115. 		g.bfs(0);
  116. 	}
  117. }
  118.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Node poped is : 0
Connected Nodes are : 1   2   
===================
Node poped is : 1
Connected Nodes are : 0   2   3   
===================
Node poped is : 2
Connected Nodes are : 0   1   3   
===================
Node poped is : 3
Connected Nodes are : 2   1   
===================
https://ideone.com/N9wNk3
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!