In last post Depth first search, we discussed recursive and iterative way to traverse a graph depth first. In this post, we are going to learn another traversal method called Breadth First Search (BFS).
Breadth First Search
First of all, what is breadth first search? In BFS, all neighbors of a node are visited before any of neighbor of those neighbors. Basically, we traverse graph layer by layer. For example, BFS of below graph would be 1->2->6->3->5->4
In depth first search, we go deep into the graph till there is not further move possible and then backtrack and again do the same process with another neighbor of parent and so on till we don’t have any further node to visit.
In breadth first search, as we traverse layer by layer, there is no backtracking required. Before reaching to layer i, all the nodes till layer i-1 would have been already visited.
Start from node S. Let S be node u. Mark it as visited. Visit all nodes which are at one edge distance from u. Once all nodes are visited, make each neighbor node as u one by one and repeat above steps till the time there is some unexplored edges. Below figure explains step by step how BFS done.
Implementation wise, BFS uses queue unlike DFS which uses stack. While processing node, all neighbors of that node are enqueued in queue and processed one after the other in FIFO order. This ensures that all nodes at same level are processed before next level is started.
Breadth-First-Search(Graph,root): for each node u in Graph: create empty queue Q Q.enqueue(root) while Q is not empty: current=Q.dequeue() print current->value visited[v] = true for each v that is adjacent to current and not visited Q.enqueue(v)
Below figure explains how breadth first implementation works
Breadth first search implementation
Applications of BFS
1. To find shortest path between two nodes u and v in an unweighted graph.
2. In Peer to Peer Networks like BitTorrent, Breadth First Search is used to find all neighbor nodes.
3. Search engine crawlers, each page leads to more pages linked to current page and so on.
4. Social networks, BFS is used to find degree of separation, friends within K distance etc.
6. Broadcasting protocol in networks uses BFS to broadcast packets to all neighboring devices.
7. To test bipartite-ness of a graph
8. To find all nodes within one connected component of graph.
9. Search for connected components in the graph for O(E+V). To do this, run start BFS from each vertex, except for vertices visited in previous runs. Do not reset each time the array visited, due to which every time we get a new connected component, and the total running time will be still O(E+V).
10. Finding solution to problem defined by statement with the least number of moves, each state of game is represented by a vertex of graph, and the transitions from one state to the other represented as edges of graph.
Finding the shortest cycle in a directed unweighted graph: produce a breadth-first search from each vertex; as soon as we try to bypass the process to go from the current peaks on some edge to an already visited vertex, then it means that we have found the shortest cycle, and stop bypassing wide found among all such cycles (one from each startup bypass) choose the shortest.
Complexity of Breadth First Search is O(|V| +|E|) where V is number of vertices in graph and E is number of edges in graph.
Please share if something is wrong or missing. If you are interested in contributing to website and share you knowledge, please refer to Publishing on Algorithms and Me and contact us. We would love to publish you articles and pay you too.