👉BFS (Breadth-First Search) – Introduction

Breadth-First Search (BFS) is a fundamental graph traversal algorithm used to visit all vertices of a graph in a breadth-wise (level-by-level) manner. Starting from a given source vertex, BFS explores all its adjacent vertices first before moving on to vertices at the next level.

BFS uses a queue data structure to keep track of vertices to be visited and a visited array to avoid revisiting the same vertex. It is especially useful for finding the shortest path in an unweighted graph and for level-order traversal.

Key Characteristics of BFS:

Traversal Type: Level-by-level (or layer-by-layer).
Data Structure Used: Queue (First In, First Out — FIFO).
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V), as it stores vertices in the queue.
Applicable To: Both graphs and trees.

How BFS Works

BFS uses a queue to store nodes to be explored and a visited list to ensure nodes aren’t visited multiple times. Here are the steps:

Initialize: Start from the root node (or any arbitrary node in a graph), mark it as visited, and enqueue it.
Dequeue and Explore: Dequeue the front node from the queue and explore its neighbors (all nodes connected by an edge).
Enqueue Neighbors: For each unvisited neighbor, mark it as visited and add it to the queue.
Repeat: Repeat the process until the queue is empty.

Pseudocode for BFS

Here’s a simple step-by-step pseudocode for BFS:

Step-by-step Visual Representation of BFS:

Step1: Initially queue and visited arrays are empty.

Step2: Push 0 into queue and mark it visited.

Step 3: Remove 0 from the front of queue and visit the unvisited neighbours and push them into queue.

Step 4: Remove node 1 from the front of queue and visit the unvisited neighbours and push them into queue.

Step 5: Remove node 2 from the front of queue and visit the unvisited neighbours and push them into queue.

Step 6: Remove node 3 from the front of queue and visit the unvisited neighbours and push them into queue. As we can see that every neighbours of node 3 is visited, so move to the next node that are in the front of the queue.