Breadth-First Search

Explores all neighbors at the current depth before moving deeper, using a queue to process nodes level by level.

Complexity

Time (Worst)

O(V + E)

Space

O(V)

Key Points

›Processes nodes level by level — guarantees shortest path in unweighted graphs
›Uses a queue (FIFO) to maintain the frontier
›Mark nodes as visited before enqueuing to avoid processing the same node twice
›Space O(V) — the queue can hold up to all vertices in the worst case
›Applications: shortest path, level-order traversal, nearest neighbor, bipartiteness check

Code Examples

Swift

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

    visited.insert(start)

    while !queue.isEmpty {
        let node = queue.removeFirst()
        result.append(node)
        for neighbor in graph[node] ?? [] where !visited.contains(neighbor) {
            visited.insert(neighbor)
            queue.append(neighbor)
        }
    }
    return result
}

let graph = [0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]]
print(bfs(graph: graph, start: 0))  // [0, 1, 2, 3, 4, 5]

Practice Problems

Binary Tree Level Order Traversal

MediumLeetCode ↗

Number of Islands

MediumLeetCode ↗

Course Schedule

MediumLeetCode ↗

Word Ladder

HardLeetCode ↗