Graphs: Breadth‐first search - rFronteddu/general_wiki GitHub Wiki

Given a graph G = (V,E) and a source vertex s, BFS explores the graph to:

• Discover all vertices reachable from s
• Computes the shortest distance from s to each reachable vertex.
• produces a BFS tree rooted at s, containing all reachable vertices.

For any reachable vertex v, the path from s to v in the BFS tree corresponds to the shortest path (minimum edges) from s to v in G. BFS works on both directed and undirected graphs.

Key Characteristics:

• BFS expands outward uniformly from the source, discovering all vertices at distance k before moving to distance k+1.
• Each vertex is assigned a color to track its status:
  • White: Undiscovered.
  • Gray: Discovered but not fully explored.
  • Black: Fully explored.

As BFS progresses, discovered vertices and their edges are added to the BFS tree. Each vertex has at most one parent, determined when it's first discovered.

// G expressed as adjacency list
// G.p is parent/predecessor
// G.d is distance from s
// The running time is O(V) for the initialization + O(E) for adjacency exploration

BFS(G, s)
    for u in G.V - {s}
        u.color = WHITE
        u.d = ∞
        u.p = nil

    s.color = GRAY
    s.d = 0
    s.p = nil
    
    let q be a FIFO queue
    q.add(s)

    while !q.isEmpty()
        u = q.poll()
        for each v in G.Adj[u]
            if v.color == WHITE
                v.color = GRAY
                v.d = u.d + 1
                v.p = u
                q.add(v)
        u.color = BLACK

// runs in linear time relative to the number of vertices in the path printed
// since each recursive call processes one vertex at a time
printPath(G, s, v)
    if v == s
        print s
    elseif v.p == nil
        print "no path from " s " to " v "exists"
    else 
        printPath(G, s, v.p)
        print v

Shortest Path

Define the shortest-path distance $\delta(s,v)$ from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path this distance is max. We call a shortest path any path of length $\delta(s,v)$ from s to v.

Breath-first trees

The BFS algorithm constructs a BF tree while exploring the graph. This tree corresponds to the parent (or predecessor) attributes of each vertex. For graph G = (V, E) with a source vertex s, the predecessor $G_p$ is defined as:

$$G_p = (V_p, E_p)$$

Where:

• $V_p$ = { $v \in V : v.p \neq nil$ } U {s}
• $E_p$ = { $(v.p,v) : v \in V_p$ - {s}}

The subgraph $G_p$ forms a BF tree if:

• $V_p$ consists of all vertices reachable from s
• For every vertex $v \in V_p$ $G_p$ contains a unique simple path from s to v, which is also the shortest path from s to v in G.

Since the BF tree is connected and contains no cycle, it satisfies the property that $|E_p|=|V_p| - 1$, making it a proper tree.

A proper tree is a connected, acyclic graph that has exactly n-1 edges for n vertices. In a BFS context, the predecessor subgraph forms a proper tree, meaning it includes all vertices reachable from the source and has the minimum number of edges to remain connected.