Breadth-First Search (BFS)

Algorithm Summary

Breadth-first search visits nodes layer by layer. It is commonly used to traverse trees, graphs, and two-dimensional grids, and it finds shortest paths when every edge has equal cost.

int bfs(Node start, Node target) {
    Queue<Node> queue = new ArrayDeque<>();
    Set<Node> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    int steps = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            Node current = queue.poll();
            if (current.equals(target)) return steps;

            for (Node next : current.neighbors()) {
                if (visited.add(next)) queue.offer(next);
            }
        }
        steps++;
    }
    return -1;
}

Topological sorting

A topological order is a linear ordering of a directed acyclic graph in which every prerequisite appears before the node that depends on it. Kahn's algorithm uses indegrees:

prerequisite A ──▶ course B ──▶ course D
        course C ──────────────▶ course D

1. Enqueue every node with indegree zero.
2. Remove one node, append it to the order, and decrement the indegree of every outgoing neighbor.
3. Enqueue neighbors whose indegree becomes zero.
4. If fewer than all nodes are processed, the graph contains a cycle.

Examples

Minimum Depth of Binary Tree — LC 111

The first leaf reached by a level-order traversal has the minimum depth. A leaf has neither a left nor a right child.

Binary Tree Level Order Traversal — LC 102

Capture queue.size() at the start of each outer loop. Poll exactly that many nodes into one list, enqueue their children, then append the completed level.

Word Ladder — LC 127

Treat every valid word as a graph node. Two words are adjacent when they differ by one character. BFS expands all transformations at the current distance before moving to the next, so the first time endWord is reached gives the shortest transformation length.

The Maze — LC 490

From each stop, roll in all four directions until hitting a wall, then step back once. Enqueue only unvisited stop positions. A boolean[][] is preferable to Set<int[]> because Java arrays compare by identity rather than contents.

The Maze II — LC 505

Rolling different distances makes edges weighted. Track the best known distance to every cell and process states with a min-priority queue, which is Dijkstra's algorithm rather than ordinary BFS.

PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
queue.offer(new int[]{start[0], start[1], 0});

Course Schedule — LC 207

Build an adjacency list and indegree array. Process every zero-indegree course; all courses are finishable only if the processed count equals numCourses.

Course Schedule II — LC 210

Use the same indegree algorithm, but append each processed course to the result. Return the ordering only when every course was processed; otherwise return an empty array.