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:
- For each vertex V $\varepsilon$ (V[G]-{S})
- do color [u] $\gets$ white
- Parent d[u] $ \gets $ $\infty$
- Predecessor $\pi$ [u] $\gets$ NIL
- Color [S] $\gets$ grey
- d[S] $\gets$ 0
- $\pi$ [S] $\gets $ NIL
- Q $\gets $ $\phi$
- ENQUEUE (Q,S)
- while Q $\not\equiv$ $\phi$
- do U $\gets$ DEQUEUE(Q)
- for each V $\varepsilon$ Adj [u]
- do if color [u] $ \gets$ white
- then color [v] $ \gets$ grey
- d[v] $ \gets$ d[u] +1
- $\pi$ [u] $ \gets$ u
- ENQUEUE (Q,v)
- 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