4 Nov 2013

BFS in Undirected Connected Graph

Problem Statement:
        Implement BFS Traversal in a Undirected Graph
Fig: Undirected Graph


BFS : (Breadth First Search)
The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.

To implement the above definition of BFS we have used to queue below.

Full Source Code : Link

 * Desc: BFS: using queue to visit to all nodes in a connected undirected Graph  
 public void bfs(int startNode)
  Queue<Integer> bfsQueue = new LinkedList<Integer>();

  // stating node visit status set to true
  vistedStatus.put(startNode, true);

  // start node added to Queue

   // Node poped from Queue
   int node=bfsQueue.poll();
   System.out.println("Node poped is : "+node);

   // all connected node list of a give node
   List<Integer> list=adjList.get(node);

   int size=list.size();
   System.out.print("Connected Nodes are : ");
   for(int i=0;i <size; ++i)
    int adjNode=list.get(i);
    System.out.print(adjNode +"   ");
    boolean isVisited=vistedStatus.get(adjNode);
     vistedStatus.put(adjNode, true);

Please comment and post your suggestions.

Happy Coding !! :)

No comments:

Post a Comment