Breadth-first search

Explore unweighted distance in layers.

Understand the problem

Enqueue the start and mark it visited immediately. Pop from the front and enqueue unseen neighbors. Marking on enqueue prevents duplicate frontier entries.

Java implementation

Queue<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int next : graph.get(node)) {
        if (!visited[next]) {
            visited[next] = true;
            queue.offer(next);
        }
    }
}

Time: O(V + E). Extra space: O(V). For all connected components, repeat from each unvisited vertex.

Trade-offs and pitfalls

BFS gives shortest hop count only when edges have equal weight.

Check your understanding

Explain how you reconstruct the shortest path using parent pointers.

Your study notes