BFS traversal of directed graph from a given node

Question

Hi,

My understanding of basic BFS traversal for a graph is:

BFS

{

Start from any node . Add it to que. Add it to visited array

While(que is not empty)

{

   remove head from queue. Print node;

   add all unvisited direct subchilds to que; mark them as visited  

}   


}   

However, if we have to traverse a DIRECTED graph from a given node and not all nodes are accessible from the given node [directly or indirectly] how do we use BFS for the same.

Can you please explain in this graph as well:

a=> b => d => e => d  
a=> c => d

Here if the starting node is b , we never print a and c.

Am I missing something in the algorithm.

P.S: I used HashMap<String,ArrayList> adj = new HashMap(); to create the adjacencey list to store graph

Any pointers are greatly appreciated.

Thanks.

Answer 1

You are correct in your understanding, except for the "Start from any node" part -- a BFS traversal must begin from the root node. So in your example, you would have to begin with node a, otherwise, as you have said, you will never visit it.

Answer 2

However, if we have to traverse a DIRECTED graph from a given node and not all nodes are accessible from the given node [directly or indirectly] how do we use BFS for the same.

A search algorithm traverses a graph. If you have edges that cannot be traversed and thus nodes that cannot be reached, the search will simply not find them.