Algorithm
- Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and
- then visit i.e. mark the vertex as visited and process all of v’s neighbors.
- Now that we’ve visited and processed all of v’s neighbors,
- we need to visit and process all of v’s neighbors neighbors
Pseudocode
BFS(graph G, vertex s)
\[all nodes initially unexplored\]
\-mark s as explored
let Q = queue data structure, initialized with s
while (Q not empty)
remove the first node of Q, call it v
for each edge (v, w):
if w is unexplored
mark w as explored
add w to Q (at the end)
We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w).
Example
Consider the graph
Let s be the starting vertex.
Layer 0 is node s, then a and b are layer 1. So, when layer 0 is processed, we add layer 1 to queue.
Layer n+1 gets added to the queue when we process layer n.
**Time Complexity: **
_Adjacency list implementation of graph - _O(|V|+|E|) OR O(n+m) where |V| and |E| is number of vertices and edges for adjacency list representation of graph.
_Running time for adjacency matrix _- O(|V|2) OR O(n2)
where V - number of vertices and E number of edges which can be reached from the starting vertex. Also this is time complexity for adjacency list implementation.
Applications of BFS