nextupprevious
Next:8.3 Minimum-Cost Spanning TreesUp:8.2 Depth First and Breadth First SearchPrevious:8.2 Depth First and Breadth First Search

8.2.1 Breadth-first search of undirected graph

Example: See Figure 8.3.

Assume the adjacency lists:
Vertex Adj. List
   
a (b, c, d, e)
b (a, d, e)
c (a, f, g)
d (a, b, e)
e (a, b, d)
f (c, g)
g (c, f)

 

Figure 8.3: Breadth-first search of an undirected graph
\begin{figure}\centerline{\psfig{figure=figures/Fgbfs.ps,width=4in}}\end{figure}

 


eEL,CSA_Dept,IISc,Bangalore