Breadth-First Search (BFS)

Lecture slides (PDF)

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices level by level, starting from a source vertex. It visits all vertices at distance $d$ before visiting any vertex at distance $d+1$.

BFS is particularly useful for finding shortest paths in unweighted graphs, where all edges have equal weight.

Breadth-First Search (BFS)

The BFS algorithm uses a queue to explore vertices in order of their distance from the source.

Algorithm:

1. Initialize: dist[v] = ∞ for all v, dist[source] = 0
2. Create queue Q, enqueue source
3. While Q is not empty:
   a. Dequeue vertex u
   b. For each neighbor v of u:
      i. If dist[v] = ∞:
         - dist[v] = dist[u] + 1
         - parent[v] = u
         - enqueue v

Example

Consider the following unweighted graph:

Running BFS from vertex 1 proceeds in waves, where each wave processes all vertices at the same distance. Here’s how the algorithm evolves:

Step 0: Initialize with source vertex. Queue contains only vertex 1 at distance 0.

Step 1: Process vertex 1. Discover neighbors 2 and 5 (distance 1). Queue now contains all vertices at distance 1.

Step 2: Process vertices 2 and then 5 (distance 1). Queue now contains vertices 3, 6, and 7 (distance 2).

Step 3: Process vertex 3, 6, and 7 (distance 3). Queue now contains vertex 4 (distance 4).

The shortest path distances from vertex 1 are: \(\text{dist} = [0, 1, 2, 3, 1, 2, 3]\)

Running Time

Each vertex is enqueued and dequeued at most once: $O(n)$. For each vertex, we iterate over its neighbors, which totals $O(m)$ across all vertices. The overall running time is $O(n + m)$.

Julia Implementation

function bfs(n, adj, source)
    dist = fill(Inf, n)
    parent = zeros(Int, n)
    dist[source] = 0
    
    queue = Int[source]
    head = 1
    
    while head <= length(queue)
        u = queue[head]
        head += 1
        
        for v in adj[u]
            if dist[v] == Inf
                dist[v] = dist[u] + 1
                parent[v] = u
                push!(queue, v)
            end
        end
    end
    
    return dist, parent
end

Shortest Path Reconstruction

The shortest paths from a source form a shortest-path tree rooted at the source. This is because if the shortest path from $s$ to $v$ goes through $u$, then the prefix of that path from $s$ to $u$ must also be a shortest path from $s$ to $u$ for if there is a shorter path from $s$ to $u$, then concatenating that shorter path with the edge from $u$ to $v$ would give a path from $s$ to $v$ shorter than the supposed shortest path, which is a contradiction.

The shortest-path tree for our BFS example (with source vertex 1) consists of the parent edges:

The tree contains only the edges used to discover each vertex for the first time:

Note that edges $(3,7)$, $(5,6)$, $(6,7)$ are not in the tree because those vertices were already discovered via other paths.

Example: Reconstruct the shortest path from vertex 1 to vertex 4 in the BFS example.

After running BFS, the parent array is:

parent = [0, 1, 1, 2, 5, 2, 5]
         1  2  3  4  5  6  7  (vertex indices)

Step 1: Start at target vertex 4.

Step 2: Move to parent of 4, which is vertex 2.

Step 3: Move to parent of 2, which is vertex 1 (the source).

The shortest path from vertex 1 to vertex 4 is: 1 → 2 → 4

function reconstruct_path(parent, source, target)
    if parent[target] == 0 && target != source
        return []  # No path exists
    end
    
    path = []
    current = target
    while current != 0
        pushfirst!(path, current)
        current = parent[current]
    end
    
    return path
end

Correctness

We can sketch the correctness of BFS using the following induction hypothesis. There is a point where only vertices at distance $k$ are in the queue furthermore the shortest path from the source to any vertex at distance $k$ has already been correctly computed. When we dequeue these vertices, vertices at distance $k+1$ will be discovered and enqueued, and the shortest path to them will be correctly computed as well.


Running Time of BFS

Note that we push each vertex to the queue at most once when it is first discovered in BFS then it is marked as visited and never enqueued again. When we push a vertex to the queue, we process each of its outgoing edges to discover its neighbors and enqueue any that have not yet been visited. Hence, each edge is processed twice (in undirected graphs) or once (in directed graphs). The running time of BFS is therefore $O(V + E)$.