Breadth-First Search in Graphs

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.

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.

1. Initialize a queue and a visited set.
2. Enqueue the starting node and mark it as visited.
3. While the queue is not empty:
1. Dequeue the front node.
2. Process or record the node.
3. For each adjacent node of the current node:
1. If it is not visited, enqueue it and mark it as visited.
4. Repeat until the queue is empty.

#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;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(const vector<vector<int>>& graph, int start) {
  vector<bool> visited(graph.size(), false);
  queue<int> q;

  visited[start] = true;
  q.push(start);

  while (!q.empty()) {
    int node = q.front();
    q.pop();
    cout << node << " ";

    for (int neighbor : graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        q.push(neighbor);
      }
    }
  }
}

int main() {
  vector<vector<int>> graph = {
    {1, 2},
    {0, 3},
    {0},
    {1}
  };
  cout << "BFS from node 0: ";
  bfs(graph, 0);
  return 0;
}

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []

    visited.add(start)

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

print("BFS from node 0:", bfs(graph, 0))

import java.util.*;

public class BFSGraph {
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(0));
        graph.put(3, Arrays.asList(1));

        System.out.print("BFS from node 0: ");
        bfs(graph, 0);
    }
}

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

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

  return result;
}

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1]
};

console.log("BFS from node 0:", bfs(graph, 0));

package main

import (
  "fmt"
)

func bfs(graph map[int][]int, start int) []int {
  visited := make(map[int]bool)
  queue := []int{start}
  result := []int{}

  visited[start] = true

  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    result = append(result, node)

    for _, neighbor := range graph[node] {
      if !visited[neighbor] {
        visited[neighbor] = true
        queue = append(queue, neighbor)
      }
    }
  }

  return result
}

func main() {
  graph := map[int][]int{
    0: {1, 2},
    1: {0, 3},
    2: {0},
    3: {1},
  }
  fmt.Println("BFS from node 0:", bfs(graph, 0))
}

use std::collections::{HashMap, HashSet, VecDeque};

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let mut result = vec![];

    visited.insert(start);
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        result.push(node);

        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                if visited.insert(neighbor) {
                    queue.push_back(neighbor);
                }
            }
        }
    }
    result
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, vec![1, 2]);
    graph.insert(1, vec![0, 3]);
    graph.insert(2, vec![0]);
    graph.insert(3, vec![1]);

    let result = bfs(&graph, 0);
    println!("BFS from node 0: {:?}", result);
}

fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
    val visited = mutableSetOf<Int>()
    val queue = ArrayDeque<Int>()
    val result = mutableListOf<Int>()

    visited.add(start)
    queue.add(start)

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)

        for (neighbor in graph[node] ?: emptyList()) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(neighbor)
            }
        }
    }
    return result
}

fun main() {
    val graph = mapOf(
        0 to listOf(1, 2),
        1 to listOf(0, 3),
        2 to listOf(0),
        3 to listOf(1)
    )
    println("BFS from node 0: ${bfs(graph, 0)}")
}

func bfs(graph: [Int: [Int]], start: Int) -> [Int] {
    var visited: Set<Int> = []
    var queue: [Int] = [start]
    var result: [Int] = []

    visited.insert(start)

    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)

        for neighbor in graph[node] ?? [] {
            if !visited.contains(neighbor) {
                visited.insert(neighbor)
                queue.append(neighbor)
            }
        }
    }
    return result
}

let graph = [
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
]

print("BFS from node 0:", bfs(graph: graph, start: 0))

function bfs(graph: Record<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const queue: number[] = [start];
  const result: number[] = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);

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

  return result;
}

const graph: Record<number, number[]> = {
  0: [1, 2],
  1: [0, 3],
  2: [0],
  3: [1],
};

console.log("BFS from node 0:", bfs(graph, 0));

Time complexity

Space complexity

O(V)

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