Breadth First Search (BFS) Algorithm

The Breadth First Search Algorithm is a cornerstone technique in computer science, renowned for its efficiency in traversing and searching tree or graph data structures. By exploring all neighbours of a node before moving to the next level, the BFS Algorithm ensures a thorough and level-wise exploration, making it indispensable for various applications, from networking to pathfinding.

What Is Graph Traversal Algorithms in Data Structure?

Graph traversal aims to systematically visit all vertices and edges in a graph without repeats. It includes:

• Breadth-First Search (BFS), which starts at a root node, explores all neighbors at the current depth, then proceeds to the next depth, using a queue for tracking. It's ideal for finding shortest paths in unweighted graphs.

• Depth-First Search (DFS) delves deep into the graph, exploring each branch fully before backtracking, using a stack for path tracking. Useful for puzzles, topological sorting, and identifying connected components.

Both methods underpin many advanced algorithms and find applications across network analysis, pathfinding, and social media.

What is BFS Algorithm?

Breadth-First Search (BFS) is a crucial algorithm for graph traversal, prioritizing the exploration of a node's immediate neighbors before advancing to their next-level neighbors. This strategy enables efficient searching for the shortest paths in unweighted graphs and ensures all nodes are visited systematically, starting from the closest. Employing a FIFO queue, BFS initiates from a chosen source node, exploring and marking each node by visiting adjacent unvisited ones, adding them to the queue for subsequent exploration. This process continues until the queue empties, signifying the completion of traversal.

The key to BFS is its FIFO queue usage, which facilitates node visits in their discovery order. This attribute makes BFS ideal for shortest path searches by edge count, calculating node levels from the source, or exhaustive visits within a graph's connected component. Its structured, level-by-level approach ensures comprehensive coverage, making it indispensable for various graph-related operations.

How Does the BFS Algorithm Works?

Beginning with the root node, the algorithm visits every node on a specific level before proceeding to the nodes on the subsequent level, continuing this pattern until it has visited all nodes.

This process utilizes a queue. It pushes all neighboring, unvisited nodes of the current level into the queue, marks the nodes of the current level as visited, and then removes them from the queue.

Let's see how to use a Breadth-First Search from Node A.

We need to use two data structures a Queue (for FIFO property) and a Set visited (to mark the visited nodes).

Step: 1
We pick A as the starting point and add A to the Queue. To prevent cycles, we also mark A as visited(by adding it to the visited set).

Step: 2
We remove the head of the Queue (i.e. A now). The Node was First In (inserted first) in the Queue.
We process A and pick all its neighbours that have not been visited yet(i.e., not in the visited set). Those are D, C, and E.
We add D, C, and E to the Queue and these to the visited set.

Step :3
Next, we pull the head of the Queue, , i.e. D.
We process D and consider all neighbours of D, which are A and E, but since both A and E are in the visited set, we ignore them and move forward.

Step :4
Next, we pull the head of the Queue, i.e. E.
We process E.
Then we need to consider all neighbours of E, which are A and D, but since both A and D are in the visited set, we ignore them and move forward.

Next, we pull the head of the Queue, i.e. C.
We process C.
Then we consider all neighbours of C, which are A and B. Since A is in the visited set, we ignore it. But as B has not yet been visited, we visit B and add it to the Queue.

Step 5:
Finally, we pick B from Queue, and its neighbour is C, which has already visited. We have nothing else in Queue to process, so we are done traversing the graph.

So the order in which we processed/explored the elements are: A, D, E, C, B which is the Breadth-First Search of the above Graph.

So we see that the Breadth-First Search relies on 2 other data structures i.e. A queue and a Visited Set (or Arrays).

Queue ensures that we process elements in the order they were first seen, and Set(or Arrays) can be used to identify which elements have already been visited.

Pseudocode of Breadth-First Search

Implementation of BFS Algorithm

Java Implementation

Output:

C++ Implementation

Output:

Python Implementation

Output:

Complexity of BFS Algorithm

From each V, we iterate all of the other neighbour vertices, i.e. at the other end of all of its edges, and the total edges we can have in the graph is E. Then it means Breadth-First Search works in O(E + V) time.

Since the Visited array and Queue can have a max size of V(equal to as many vertices), the overall space complexity will be O(V).

Applications of Breadth First Search (BFS) Algorithm

Let's explore the various applications of Breadth-First Search:

1. Creating minimum spanning trees for unweighted graphs: By utilizing Breadth-First Search, it's possible to navigate from any selected starting point to another with the least number of edges. This concept is pivotal in constructing a minimum spanning tree that encapsulates the shortest paths covering all vertices.

2. Peer-to-peer networks: Breadth-First Search aids in identifying a neighboring peer from any given peer within peer-to-peer networks.

3. Search engine crawlers: To index the web, search engines employ Breadth-First Search to systematically visit and catalog web pages starting from a source page and progressing through linked pages.

4. GPS navigation: For determining locations within a specific distance from a starting point, Breadth-First Search is employed to locate and explore neighboring areas up to a defined radius.

5. Network broadcasting: In the process of broadcasting from a source, the identification and subsequent broadcasting to neighboring nodes are achieved through Breadth-First Search, continuing this pattern recursively.

6. Pathfinding: Breadth-First Search is utilized to discover a route between two points by starting from one vertex and traversing until the other is reached. If the search exhausts all reachable vertices without finding the target, it indicates no available path.

7. Identifying all accessible nodes from a specific vertex: In any graph, especially disconnected ones, all nodes accessible from a particular starting point can be determined through Breadth-First Search. The completion of this search marks certain vertices as visited, denoting all nodes that can be reached.

See more:

• Breadth First Search in Python
• BFS Program in C
• Difference Between BFS and DFS