BFS in Data Structure

BFS is an easy and simplest algorithm for searching a graph and this algorithm works on both directed and Undirected graph .Many algorithm uses the idea of BFS like prism algorithm and Dijkstra Algorithm.

Given a graph G = {V,E} and a distinguished source vertex ‘S’ . BFS Systematically explores the edges of G to discover every vertex that is reachable from ‘S’ .It completes distance from ‘S’ it computes distance from ‘S’ to each reachable vertex.

BFS Algorithm With Explanation:

1. For each vertex V $\varepsilon$ (V[G]-{S})
2. do color [u] $\gets$ white
3. Parent d[u] $ \gets $ $\infty$
4. Predecessor $\pi$ [u] $\gets$ NIL
5. Color [S] $\gets$ grey
6. d[S] $\gets$ 0
7. $\pi$ [S] $\gets $ NIL
8. Q $\gets $ $\phi$
9. ENQUEUE (Q,S)
10. while Q $\not\equiv$ $\phi$
11. do U $\gets$ DEQUEUE(Q)
12. for each V $\varepsilon$ Adj [u]
13. do if color [u] $ \gets$ white
14. then color [v] $ \gets$ grey
15. d[v] $ \gets$ d[u] +1
16. $\pi$ [u] $ \gets$ u
17. ENQUEUE (Q,v)
18. color [u] $ \gets$ black

Lines 1-4 point every vertex white, set d[u] to be infinite and set parent of every vertex nil.

Lines 5 point the source vertex as grey since it is considered to be discovered.

Line 6-7 initializes d[s] to 0 and set the predecessor of source to be nil.

Line 8-9 initialize Q, queue containing that the vertex ‘S’

Line 10-18 while loop iterates as long as their remain any grey vertex.

• BFS color each node white, grey or black to keep the track of program.
• All vertices discard out white and later become grey or white
• A vertex is called discovered when it is encountered first time during the search and at this type it become non-white