Breadth-First Search in Graphs

Problem Statement❯

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores the neighbor nodes level by level. Given a starting node in a graph, BFS visits all its adjacent nodes, then moves on to their neighbors, and so on.

BFS is commonly used for finding the shortest path in unweighted graphs, level order traversal of trees, and in many other scenarios where step-wise discovery is important.

Examples❯

Input Graph	BFS Traversal	Description
{0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}	[0, 1, 2, 3, 4]	Starting from node 0, it visits all directly connected nodes (1 and 2), then expands to 1's neighbors (3 and 4).
{10: [20, 50], 20: [10, 40], 30: [50], 40: [20, 50], 50: [10, 30, 40]}	[10, 20, 50, 40, 30]	Starting from node 10, BFS visits 20 and 50 first, then explores 50's neighbors (40 and 30). Cycles are avoided.
{1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4]}	[1, 2, 3, 4, 5]	A densely connected graph; BFS explores all layers level-by-level starting from node 1.
{1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}	[1, 2, 3, 4]	A linear chain; BFS behaves like DFS here but still visits breadth-first per level.
{0: [1], 1: [0], 2: [3], 3: [2]}	[0, 1]	Graph has two disconnected components; BFS from node 0 covers only the first component.

Solution❯

Understanding the Problem

Breadth-First Search (BFS) is a fundamental algorithm used to traverse or search nodes in a graph or tree. The core idea is to explore all nodes at the current depth level before moving on to the next level. BFS uses a queue to keep track of the order in which to visit nodes and ensures each node is visited exactly once using a visited set or array.

Let’s say you’re given a graph as an adjacency list, and you need to traverse all its nodes starting from a given source. The problem becomes even more interesting when you have disconnected graphs or cycles.

Our goal is to understand how BFS works step-by-step and handle these special scenarios properly.

Step-by-Step Solution with Example

step 1: Define the Graph

We will represent the graph using an adjacency list. For example:


const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

step 2: Understand the Starting Point

We start BFS from node 'A'. This means we will visit 'A' first and then its neighbors — 'B' and 'C'.

step 3: Use a Queue and a Visited Set

We use a queue to manage the order of visiting nodes, and a set to keep track of visited nodes to avoid revisiting.


const queue = ['A'];
const visited = new Set(['A']);

step 4: Begin the Traversal

We dequeue 'A', visit its neighbors 'B' and 'C', and add them to the queue and the visited set.


while (queue.length > 0) {
  const current = queue.shift();
  console.log(current); // print visited node

  for (const neighbor of graph[current]) {
    if (!visited.has(neighbor)) {
      queue.push(neighbor);
      visited.add(neighbor);
    }
  }
}

step 5: Track the Order of Visit

In this example, the BFS traversal order will be: A → B → C → D.

step 6: Print or Store the Result

You can print each visited node, or store them in an array for further analysis.

Edge Cases

1. Disconnected Graph

If the graph has multiple disconnected components, starting BFS from one node will only cover its connected component. To visit all nodes, run BFS for each unvisited node:


for (const node in graph) {
  if (!visited.has(node)) {
    bfs(node);
  }
}

2. Graph with Cycles

Cycles can cause infinite loops if visited nodes are not tracked. Always use a visited set to mark nodes that have already been added to the queue.

3. Self-loops

A node may have an edge to itself (e.g., A: ['A']). The visited set will ensure it’s not processed again and again.

4. Empty Graph

If the graph is empty, return an empty traversal list. Always check for this condition before starting BFS.

Finally

BFS is a powerful and intuitive graph traversal algorithm especially useful for problems involving levels, shortest paths in unweighted graphs, or connectivity checks. By thinking of BFS like spreading a message — where each person tells all their immediate friends first — you can intuitively understand how it works. With careful use of a queue and visited tracking, you can avoid pitfalls like cycles or missed components in disconnected graphs.

Always test your implementation against edge cases like cycles, disconnected graphs, and empty inputs to ensure robustness.

Algorithm Steps❯

Initialize a queue and a visited set.
Enqueue the starting node and mark it as visited.
While the queue is not empty:

Dequeue the front node.
Process or record the node.
For each adjacent node of the current node:

If it is not visited, enqueue it and mark it as visited.

Repeat until the queue is empty.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdbool.h>
#define MAX 100

int queue[MAX], front = 0, rear = 0;
bool visited[MAX];

void enqueue(int v) {
  queue[rear++] = v;
}

int dequeue() {
  return queue[front++];
}

bool isEmpty() {
  return front == rear;
}

void bfs(int graph[MAX][MAX], int vertices, int start) {
  for (int i = 0; i < vertices; i++) visited[i] = false;

  enqueue(start);
  visited[start] = true;

  while (!isEmpty()) {
    int node = dequeue();
    printf("%d ", node);

    for (int i = 0; i < vertices; i++) {
      if (graph[node][i] && !visited[i]) {
        enqueue(i);
        visited[i] = true;
      }
    }
  }
}

int main() {
  int graph[MAX][MAX] = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 0},
    {0, 1, 0, 0}
  };
  printf("BFS from node 0: ");
  bfs(graph, 4, 0);
  return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case, BFS must explore every vertex (V) and every edge (E) to ensure complete traversal of the graph component.
Average Case	O(V + E)	On average, BFS visits all vertices and edges once during the traversal.
Worst Case	O(V + E)	In the worst case, such as a fully connected graph, BFS still processes all vertices and edges exactly once.

Space Complexity❯

O(V)

Explanation: The space complexity is proportional to the number of vertices because the queue and visited set each store up to V elements.

⬅ Previous TopicFlatten a Binary Search Tree into a Sorted List

Next Topic ⮕Depth-First Search in Graphs

Comments

Loading comments...

Breadth-First Search (BFS) in Graphs

Contents

Visualization Player

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

step 1: Define the Graph

step 2: Understand the Starting Point

step 3: Use a Queue and a Visited Set

step 4: Begin the Traversal

step 5: Track the Order of Visit

step 6: Print or Store the Result

Edge Cases

1. Disconnected Graph

2. Graph with Cycles

3. Self-loops

4. Empty Graph

Finally

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Breadth-First Search (BFS) in Graphs

Contents

Visualization Player

Problem Statement❯

Examples❯

Solution❯

Understanding the Problem

Step-by-Step Solution with Example

step 1: Define the Graph

step 2: Understand the Starting Point

step 3: Use a Queue and a Visited Set

step 4: Begin the Traversal

step 5: Track the Order of Visit

step 6: Print or Store the Result

Edge Cases

1. Disconnected Graph

2. Graph with Cycles

3. Self-loops

4. Empty Graph

Finally

Algorithm Steps❯

Code

Time Complexity❯

Space Complexity❯

Comments

Welcome to ProgramGuru

Player Settings