Breadth First Search

Breadth First Search is a graph traversal algorithm.

The breadth-first search begins at the root node of the graph and explores all its neighbouring nodes. For each of these nodes, the algorithm again explores its neighbouring nodes. This is continued until the specified element is found or all the nodes are exhausted.

A queue is used as an auxiliary data structure to keep track of the neighbouring nodes.

Properties

Time Complexity

The worst case occurs when the algorithm has to traverse through all the nodes in the graph. Therefore the sum of the vertices(V) and the edges(E) is the worst-case scenario. This can be expressed as O( |E| + |V| ).

Space Complexity

During the traversal, all the nodes at one level must be stored until their child nodes in the next level have been visited. The space complexity is, therefore, the deepest level of the nodes in the graph.

Completeness

This is a complete algorithm because if there exists a solution, it will be found regardless of the type of graph provided.

Algorithm

1. Define a Queue with the size equal to the total number of vertices in the graph.
2. Select any vertex as the starting point for traversal. Visit that vertex and insert it into the Queue.
3. Visit all the adjacent vertices of the vertex which is in front of the Queue which is not visited and insert them into the Queue.
4. When there is no new vertex to visit from the vertex at front of the Queue then delete that vertex from the Queue.
5. Repeat step 3 and 4 until the queue becomes empty.
6. When the queue becomes Empty, then produce the final spanning tree by removing unused edges from the graph.

Applications

1. Peer to Peer Networks: In a peer to peer network, all the nodes are required to keep track of its neighbouring nodes. Breadth First Search can be used for this purpose.
2. Search Engine Crawlers: Search Engines crawlers keep track of all the pages of the web by maintaining a list of all pages and their neighbours. Using Breadth First Search allows keeping a limit on the depth of the pages traversed by the crawlers.
3. Path Finding and GPS Navigation: The path from one point to another point can be found using a Breadth First Search. This is used in GPS navigation systems we use every day.

Visualisations

Breadth First Search Visualisation: Excellent visualization from cs.usfca.edu

Videos

Breadth First Search: Excellent explanation from MIT OCW