Sign in Subscribe

BFS (Breadth-First Search algorithm)

Last updated on 

Introduction

Breadth-First Search (BFS) is a popular algorithm used to traverse a graph. It is a systematic algorithm that explores all the vertices in the graph at a given depth before moving on to the vertices at the next depth. The algorithm starts at the root node and visits all the vertices that are one level away from the root node before moving on to the vertices that are two levels away, and so on. BFS is often used to find the shortest path between two vertices in an unweighted graph or to find the minimum number of steps required to solve a puzzle.

Algorithm

The BFS algorithm works as follows:

  1. Create a queue and enqueue the starting node.
  2. Create a set to keep track of visited nodes.
  3. While the queue is not empty, dequeue the first node in the queue.
  4. If the dequeued node is the goal node, return success and stop.
  5. Otherwise, mark the dequeued node as visited and add all its adjacent nodes to the queue if they have not been visited before.
  6. Repeat steps 3 to 5 until the queue is empty.

Let's go through each step in more detail.

Create a queue and enqueue the starting node.

The first step in the BFS algorithm is to create a queue and enqueue the starting node. The starting node is the node from which the BFS algorithm will begin the traversal. The queue is a data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element to be inserted into the queue will be the first element to be removed from the queue. In the context of the BFS algorithm, the queue will be used to keep track of the nodes that need to be visited.

Create a set to keep track of visited nodes.

The second step is to create a set to keep track of the nodes that have been visited. This set is used to ensure that the BFS algorithm does not visit the same node multiple times. Visiting a node multiple times can lead to an infinite loop if there are cycles in the graph.

While the queue is not empty, dequeue the first node in the queue.

The third step is to start the traversal of the graph. This is done by using a while loop that continues until the queue is empty. Inside the while loop, the first node in the queue is dequeued. Dequeuing a node means removing it from the front of the queue. This is done using the dequeue operation.

If the dequeued node is the goal node, return success and stop.

The fourth step is to check if the dequeued node is the goal node. The goal node is the node that the BFS algorithm is searching for. If the dequeued node is the goal node, the algorithm has successfully found the node and can return success. The algorithm then stops.

Otherwise, mark the dequeued node as visited and add all its adjacent nodes to the queue if they have not been visited before.

The fifth step is to visit the dequeued node. This is done by marking the node as visited. The visited nodes are added to the set created in step 2. The adjacent nodes of the dequeued node are then added to the queue if they have not been visited before. Adding a node to the queue means enqueueing it at the back of the queue. This is done using the enqueue operation.

Repeat steps 3 to 5 until the queue is empty.

The sixth step is to repeat steps 3 to 5 until the queue is empty. This means that all the nodes in the graph have been visited. The BFS algorithm will visit all the nodes in the graph in a breadth-first manner.

Example

Let's use an example to illustrate how the BFS algorithm works. Consider the following graph:

Suppose we want to use the BFS algorithm to find the shortest path between nodes A and G. We can start by enqueuing node A and creating a set to keep track of the visited nodes.cssCopy codequeue: [A] visited: {A}

Next, we dequeue node A and visit its adjacent nodes, which are B and C. We add B and C to the queue and mark them as visited.cssCopy codequeue: [B, C] visited: {A, B, C}

We then dequeue node B and visit its adjacent node, which is D. We add D to the queue and mark it as visited.cssCopy codequeue: [C, D] visited: {A, B, C, D}

We dequeue node C and visit its adjacent nodes, which are E and F. We add E and F to the queue and mark them as visited.cssCopy codequeue: [D, E, F] visited: {A, B, C, D, E, F}

We dequeue node D and visit its adjacent node, which is G. We have found the goal node, so we return success and stop.cssCopy codequeue: [E, F, G] visited: {A, B, C, D, E, F, G}

In this example, the shortest path between nodes A and G is A -> C -> F -> G. This is because these are the nodes that were visited by the BFS algorithm in the order they were visited.

Time Complexity

The time complexity of the BFS algorithm is O(V+E), where V is the number of vertices in the graph and E is the number of edges in the graph. This is because each vertex and edge is visited exactly once. The space complexity of the BFS algorithm is also O(V+E), as the algorithm needs to store the visited nodes and the nodes in the queue.

Conclusion

Breadth-First Search is a popular algorithm used to traverse a graph in a systematic way. It explores all the vertices in the graph at a given depth before moving on to the vertices at the next depth. The BFS algorithm is often used to find the shortest path between two vertices in an unweighted graph or to find the minimum number of steps required to solve a puzzle. The algorithm has a time complexity of O(V+E) and a space complexity of O(V+E).