Breadth-First Search (BFS)

Implement breadth-first search traversal of a graph

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

Implement a breadth-first search (BFS) traversal algorithm for a graph. Given a graph represented as an adjacency list and a starting vertex, perform BFS traversal and return the order in which vertices are visited.

Input:

  • Graph represented as adjacency list (map/dictionary)
  • Starting vertex

Output:

  • List of vertices in BFS traversal order

Constraints:

  • Graph can have 1-10^4 vertices
  • Graph can be directed or undirected
  • Graph may have disconnected components
  • Vertices can be represented as integers or strings

Examples:

Example 1:

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

Output: [0, 1, 2, 3, 4]

Explanation: Starting from vertex 0, visit neighbors 1 and 2, then neighbors of 1 (3 and 4).

Example 2:

Input:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
start = 'A'

Output: ['A', 'B', 'C', 'D', 'E', 'F']

Example 3 (Disconnected Graph):

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

Output: [0, 1]

Explanation: Only vertices connected to starting vertex 0 are visited.

Solutions

Approach 1: Iterative BFS with Queue

BFS explores the graph level by level, visiting all vertices at distance k before visiting vertices at distance k+1.

Algorithm:

  1. Create a queue and add the starting vertex
  2. Create a visited set to track visited vertices
  3. While queue is not empty:
    • Dequeue a vertex
    • If not visited, mark as visited and add to result
    • Enqueue all unvisited neighbors
  4. Return the traversal order

Python:

from collections import deque

def bfs_traversal(graph, start):
    """
    Perform BFS traversal on a graph
    Time: O(V + E)
    Space: O(V)
    """
    visited = set()
    result = []
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        # Visit all neighbors
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

def bfs_all_components(graph):
    """
    BFS traversal for all components in disconnected graph
    Time: O(V + E)
    Space: O(V)
    """
    visited = set()
    result = []
    
    for vertex in graph:
        if vertex not in visited:
            component = []
            queue = deque([vertex])
            visited.add(vertex)
            
            while queue:
                v = queue.popleft()
                component.append(v)
                
                for neighbor in graph.get(v, []):
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            
            result.extend(component)
    
    return result

Java:

import java.util.*;

class Solution {
    /**
     * Perform BFS traversal on a graph
     * Time: O(V + E)
     * Space: O(V)
     */
    public List<Integer> bfsTraversal(Map<Integer, List<Integer>> graph, int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            result.add(vertex);
            
            // Visit all neighbors
            List<Integer> neighbors = graph.getOrDefault(vertex, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
    
    /**
     * BFS traversal for all components in disconnected graph
     * Time: O(V + E)
     * Space: O(V)
     */
    public List<Integer> bfsAllComponents(Map<Integer, List<Integer>> graph) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        
        for (int vertex : graph.keySet()) {
            if (!visited.contains(vertex)) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(vertex);
                visited.add(vertex);
                
                while (!queue.isEmpty()) {
                    int v = queue.poll();
                    result.add(v);
                    
                    List<Integer> neighbors = graph.getOrDefault(v, new ArrayList<>());
                    for (int neighbor : neighbors) {
                        if (!visited.contains(neighbor)) {
                            visited.add(neighbor);
                            queue.offer(neighbor);
                        }
                    }
                }
            }
        }
        
        return result;
    }
}

Go:

// bfsTraversal - Perform BFS traversal on a graph
// Time: O(V + E)
// Space: O(V)
func bfsTraversal(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    result := []int{}
    queue := []int{start}
    visited[start] = true
    
    for len(queue) > 0 {
        vertex := queue[0]
        queue = queue[1:]
        result = append(result, vertex)
        
        // Visit all neighbors
        neighbors, exists := graph[vertex]
        if exists {
            for _, neighbor := range neighbors {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
    }
    
    return result
}

// bfsAllComponents - BFS traversal for all components in disconnected graph
// Time: O(V + E)
// Space: O(V)
func bfsAllComponents(graph map[int][]int) []int {
    visited := make(map[int]bool)
    result := []int{}
    
    for vertex := range graph {
        if !visited[vertex] {
            queue := []int{vertex}
            visited[vertex] = true
            
            for len(queue) > 0 {
                v := queue[0]
                queue = queue[1:]
                result = append(result, v)
                
                neighbors, exists := graph[v]
                if exists {
                    for _, neighbor := range neighbors {
                        if !visited[neighbor] {
                            visited[neighbor] = true
                            queue = append(queue, neighbor)
                        }
                    }
                }
            }
        }
    }
    
    return result
}

JavaScript:

/**
 * Perform BFS traversal on a graph
 * Time: O(V + E)
 * Space: O(V)
 */
function bfsTraversal(graph, start) {
    const visited = new Set();
    const result = [];
    const queue = [start];
    visited.add(start);
    
    while (queue.length > 0) {
        const vertex = queue.shift();
        result.push(vertex);
        
        // Visit all neighbors
        const neighbors = graph[vertex] || [];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    
    return result;
}

/**
 * BFS traversal for all components in disconnected graph
 * Time: O(V + E)
 * Space: O(V)
 */
function bfsAllComponents(graph) {
    const visited = new Set();
    const result = [];
    
    for (const vertex in graph) {
        if (!visited.has(vertex)) {
            const queue = [vertex];
            visited.add(vertex);
            
            while (queue.length > 0) {
                const v = queue.shift();
                result.push(v);
                
                const neighbors = graph[v] || [];
                for (const neighbor of neighbors) {
                    if (!visited.has(neighbor)) {
                        visited.add(neighbor);
                        queue.push(neighbor);
                    }
                }
            }
        }
    }
    
    return result;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Perform BFS traversal on a graph
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    public List<int> BfsTraversal(Dictionary<int, List<int>> graph, int start) {
        var result = new List<int>();
        var visited = new HashSet<int>();
        var queue = new Queue<int>();
        
        queue.Enqueue(start);
        visited.Add(start);
        
        while (queue.Count > 0) {
            int vertex = queue.Dequeue();
            result.Add(vertex);
            
            // Visit all neighbors
            if (graph.TryGetValue(vertex, out List<int> neighbors)) {
                foreach (int neighbor in neighbors) {
                    if (!visited.Contains(neighbor)) {
                        visited.Add(neighbor);
                        queue.Enqueue(neighbor);
                    }
                }
            }
        }
        
        return result;
    }
    
    /// <summary>
    /// BFS traversal for all components in disconnected graph
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    public List<int> BfsAllComponents(Dictionary<int, List<int>> graph) {
        var result = new List<int>();
        var visited = new HashSet<int>();
        
        foreach (int vertex in graph.Keys) {
            if (!visited.Contains(vertex)) {
                var queue = new Queue<int>();
                queue.Enqueue(vertex);
                visited.Add(vertex);
                
                while (queue.Count > 0) {
                    int v = queue.Dequeue();
                    result.Add(v);
                    
                    if (graph.TryGetValue(v, out List<int> neighbors)) {
                        foreach (int neighbor in neighbors) {
                            if (!visited.Contains(neighbor)) {
                                visited.Add(neighbor);
                                queue.Enqueue(neighbor);
                            }
                        }
                    }
                }
            }
        }
        
        return result;
    }
}

Approach 2: BFS with Level Order Tracking

This approach tracks which level each vertex belongs to, useful for problems requiring level-wise processing.

Python:

def bfs_with_levels(graph, start):
    """
    BFS with level tracking
    Time: O(V + E)
    Space: O(V)
    """
    visited = set()
    levels = []
    queue = deque([(start, 0)])
    visited.add(start)
    current_level = 0
    current_level_nodes = []
    
    while queue:
        vertex, level = queue.popleft()
        
        if level > current_level:
            levels.append(current_level_nodes)
            current_level_nodes = []
            current_level = level
        
        current_level_nodes.append(vertex)
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, level + 1))
    
    if current_level_nodes:
        levels.append(current_level_nodes)
    
    return levels

Java:

public List<List<Integer>> bfsWithLevels(Map<Integer, List<Integer>> graph, int start) {
    /**
     * BFS with level tracking
     * Time: O(V + E)
     * Space: O(V)
     */
    List<List<Integer>> levels = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Queue<int[]> queue = new LinkedList<>();
    
    queue.offer(new int[]{start, 0});
    visited.add(start);
    
    List<Integer> currentLevel = new ArrayList<>();
    int currentLevelNum = 0;
    
    while (!queue.isEmpty()) {
        int[] item = queue.poll();
        int vertex = item[0];
        int level = item[1];
        
        if (level > currentLevelNum) {
            levels.add(new ArrayList<>(currentLevel));
            currentLevel.clear();
            currentLevelNum = level;
        }
        
        currentLevel.add(vertex);
        
        List<Integer> neighbors = graph.getOrDefault(vertex, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(new int[]{neighbor, level + 1});
            }
        }
    }
    
    if (!currentLevel.isEmpty()) {
        levels.add(currentLevel);
    }
    
    return levels;
}

Go:

type NodeLevel struct {
    node  int
    level int
}

// bfsWithLevels - BFS with level tracking
// Time: O(V + E)
// Space: O(V)
func bfsWithLevels(graph map[int][]int, start int) [][]int {
    visited := make(map[int]bool)
    levels := [][]int{}
    queue := []NodeLevel{{start, 0}}
    visited[start] = true
    
    currentLevel := []int{}
    currentLevelNum := 0
    
    for len(queue) > 0 {
        item := queue[0]
        queue = queue[1:]
        
        if item.level > currentLevelNum {
            levels = append(levels, currentLevel)
            currentLevel = []int{}
            currentLevelNum = item.level
        }
        
        currentLevel = append(currentLevel, item.node)
        
        if neighbors, exists := graph[item.node]; exists {
            for _, neighbor := range neighbors {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, NodeLevel{neighbor, item.level + 1})
                }
            }
        }
    }
    
    if len(currentLevel) > 0 {
        levels = append(levels, currentLevel)
    }
    
    return levels
}

JavaScript:

/**
 * BFS with level tracking
 * Time: O(V + E)
 * Space: O(V)
 */
function bfsWithLevels(graph, start) {
    const visited = new Set();
    const levels = [];
    const queue = [[start, 0]];
    visited.add(start);
    
    let currentLevel = [];
    let currentLevelNum = 0;
    
    while (queue.length > 0) {
        const [vertex, level] = queue.shift();
        
        if (level > currentLevelNum) {
            levels.push([...currentLevel]);
            currentLevel = [];
            currentLevelNum = level;
        }
        
        currentLevel.push(vertex);
        
        const neighbors = graph[vertex] || [];
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, level + 1]);
            }
        }
    }
    
    if (currentLevel.length > 0) {
        levels.push(currentLevel);
    }
    
    return levels;
}

C#:

public List<List<int>> BfsWithLevels(Dictionary<int, List<int>> graph, int start) {
    /// <summary>
    /// BFS with level tracking
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    var levels = new List<List<int>>();
    var visited = new HashSet<int>();
    var queue = new Queue<(int vertex, int level)>();
    
    queue.Enqueue((start, 0));
    visited.Add(start);
    
    var currentLevel = new List<int>();
    int currentLevelNum = 0;
    
    while (queue.Count > 0) {
        var (vertex, level) = queue.Dequeue();
        
        if (level > currentLevelNum) {
            levels.Add(new List<int>(currentLevel));
            currentLevel.Clear();
            currentLevelNum = level;
        }
        
        currentLevel.Add(vertex);
        
        if (graph.TryGetValue(vertex, out List<int> neighbors)) {
            foreach (int neighbor in neighbors) {
                if (!visited.Contains(neighbor)) {
                    visited.Add(neighbor);
                    queue.Enqueue((neighbor, level + 1));
                }
            }
        }
    }
    
    if (currentLevel.Count > 0) {
        levels.Add(currentLevel);
    }
    
    return levels;
}

Key Insights

  1. Queue-Based Traversal: BFS uses a queue (FIFO) to explore vertices level by level
  2. Visited Set: Essential to prevent revisiting vertices and infinite loops in cyclic graphs
  3. Level-Order Processing: BFS naturally processes vertices in increasing order of distance from start
  4. Space Complexity: BFS may use more space than DFS when the branching factor is high

Edge Cases

  1. Empty graph: Return empty list
  2. Single vertex: Return list with one element
  3. Disconnected components: Only vertices reachable from start are visited
  4. Self-loops: Handled by visited set
  5. Multiple edges between vertices: Visited set prevents redundant processing
  6. Start vertex not in graph: Return empty or single element list

Common Mistakes

  1. Not marking vertices as visited immediately: Can lead to vertices being added to queue multiple times
  2. Using stack instead of queue: This would implement DFS, not BFS
  3. Not handling disconnected components: May miss vertices in separate components
  4. Modifying graph during traversal: Can lead to unexpected behavior

Follow-up Questions

  1. Shortest Path: How would you find the shortest path between two vertices?
  2. Bipartite Check: How would you check if a graph is bipartite using BFS?
  3. Connected Components: How would you count the number of connected components?
  4. Minimum Distance: How would you find minimum distance from source to all vertices?
  5. Level Order in Tree: How does BFS differ when applied to a tree vs general graph?