SKEDSOFT

Artificial Intelligence

Analysis

Before proving the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, as we saw in Aggregate analysis. After initialization, no vertex is ever whitened, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O(V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of BFS is O(V E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G.

Shortest paths

At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G = (V, E) from a given source vertex s V. Define the shortest-path distance δ(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 from s to v, then δ(s, v) = . A path of length δ(s, v) from s to v is said to be a shortest path from s to v. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances.

Breadth-first trees

The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 22.3. The tree is represented by the π field in each vertex. More formally, for a graph G = (V, E) with source s, we define the predecessor subgraph of G as Gπ = (Vπ, Eπ), where

Vπ = {v V: π[v] NIL} { s}

and

Eπ = {(π[v], v) : v Vπ - {s}}.

The predecessor subgraph Gπ is a breadth-first tree if Vπ consists of the vertices reachable from s and, for all v Vπ , there is a unique simple path from s to v in Gπ that is also a shortest path from s to v in G. A breadth-first tree is in fact a tree, since it is connected and |Eπ| = |Vπ| - 1. The edges in Eπ are called tree edges.

After BFS has been run from a source s on a graph G, the following lemma shows that the predecessor subgraph is a breadth-first tree.