Algorithms in a Nutshell

Breadth-First Search | 151

Graph

Algorithms

Input/Output

Input

A graphG=(V,E) and a source vertexs∈V. The quantitynrepresents the number

of vertices inG.

Output

BREADTH-FIRSTSEARCHproduces two computed arrays.dist[v]determines the

number of edges in a shortest path fromstov.pred[v]determines the prede-

cessor vertex ofvbased on the breadth-first search ordering. Thepred[]values

will encode the breadth-first tree search result; if the original graph is uncon-

nected, then all verticesw unreachable froms have apred[w] value of –1.

Assumptions

The algorithm works for undirected as well as directed graphs.

Context

BREADTH-FIRSTSEARCHstores the vertices that are still “at play” within a queue,

and thus there may be a non-trivial storage space required for very large graphs.

BREADTH-FIRSTSEARCHis guaranteed to find a shortest path in graphs whose

vertices are generated “on the fly” (as will be seen in Chapter 7). Indeed, all paths

in the generated breadth-first tree are shortest paths froms in terms of edge count.

Figure 6-12. Breadth-First Search progress on graph when counter reaches 18

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use