Breadth-First Search | 149GraphAlgorithmsBack edges
Whendfs_visit(u)encounters a vertexvthat is adjacent touand is already
colored gray, then DEPTH-FIRSTSEARCHdetects it is revisiting old ground.
The edge (8,s) is an example in Figure 6-10.
Forward edges
Whendfs_visit(u)encounters a vertexvthat is adjacent touand is already
marked black, the edge (u,v) is a forward edge if vertexuwas visited beforev.
Again, DEPTH-FIRSTSEARCHdetects it is revisiting old ground. The edge
(5,9) is an example in Figure 6-10.
Cross edges
Whendfs_visit(u)encounters a vertexvthat is adjacent touand is already
marked black, the edge (u,v) is a cross edge if vertexvwas visited beforeu.
Cross edges are possible only in directed graphs.
The code to compute these edge labels is included in Example 6-1. For undi-
rected graphs, the edge (u,v) may be labeled multiple times; it is common to
accept the labeling the first time an edge is encountered, whether as (u,v)oras
(v,u).Analysis
The recursivedfs_visitfunction is called once for each vertex in the graph. The
loop in thedfs_searchfunction is executed no more thanntimes. Withindfs_
visit, every neighboring vertex must be checked; for directed graphs, each edge is
traversed once, whereas in undirected graphs they are traversed once and are seen
one other time. In any event, the total performance cost is O(V+E).Breadth-First Search
BREADTH-FIRSTSEARCH(shown in Figure 6-11) takes a different approach from
DEPTH-FIRSTSEARCHwhen searching a graph. BREADTH-FIRSTSEARCHsystem-
atically visits all vertices in the graphG=(V,E) that arekedges away from the
source vertexsbefore visiting any vertex that isk+1edges away. This process
repeats until no more vertices are reachable froms.BREADTH-FIRSTSEARCHdoes
not visit vertices inG that are not reachable froms.
BREADTH-FIRSTSEARCHmakes its progress without requiring any backtracking.
It records its progress by coloring vertices white, gray, and black, as DEPTH-FIRST
SEARCHdid. Indeed, the same colors and definitions apply. To compare directly
with DEPTH-FIRSTSEARCH, we can construct a similar notion of a counter that
increments when a vertex is first visited (and colored gray) and when the vertex is last
visited (and colored black). Given the graph used earlier in Figure 6-8, in the same
amount of time (i.e., when the counter reaches 18), BREADTH-FIRSTSEARCHis able
to progress to the state shown in Figure 6-12, where vertex 12 has just been colored
gray.Note that BREADTH-FIRSTSEARCHis done with vertices {1,6,8}, which
are one edge away froms, and vertices {2,3}, which are two edges away froms.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