BFS for Undirected Graphs

Both BFS and DFS may be used to compute connected components of an undirected graph. 

BFS

Here, s is the source vertex.  We use a queue and put s into it. Remove s first, mark as explored and insert into it a and b when we remove s. Recall that we can use an adjacency list to maintain a list of neighbours of a given node. Let us assume, a is put in first and then b.

Queue state: a,b

Now, a is taken out, marked as explored and it's adjacent nodes, c,b,s are inserted back into the queue. Queue : b,c,b,s

Take out b, mark b as explored and put it's adjacent nodes, a,c,d,s into the queue.

Queue state: c,b,s,a,c,d,s

Take out c, mark as explored and put it's neighbours, a,b,d,e into the queue.

Queue state: b,s,a,c,d,s,a,b,d,e

Take out b. But b is explored so simply proceed to the next queue element.

Take out s, s was the first item to be explored. So go on to the next element.

Take out a, explored so proceed.

Take out c, explored so proceed.

Take out d, unexplored, so mark as explored and put it's neighbours, b,c,e into the queue

Queue state: s,a,b,d,e,b,c,e

Take out s, explored so proceed.

Take out a, explored, move on.

Take out b, explored, move on.

Take out d, explored, so move on.

Take out e, unexplored, mark as explored and put it's neighbours c,d into the queue.

Queue state: b,c,e,c,d

Take out b, explored, move on.

Take out c, explored, move on.

Take out e, explored, proceed.

Take out c, explored, so proceed.

Take out d, explored, proceed.

Queue is empty. BFS completed.