Next: 13. Data Structures for Up: 12. Graphs Previous: 12.3 Graph Traversal Contents Index
The running times of the depth-first-search and breadth-first-search
algorithms are somewhat overstated by the Theorems 12.3 and
12.4. Define
as the number of vertices,
,
of 
, for which there exists a path from
to
. Define
as the number of edges that have these vertices as their sources.
Then the following theorem is a more precise statement of the running
times of the breadth-first-search and depth-first-search algorithms.
(This more refined statement of the running time is useful in some of
the applications of these algorithms outlined in the exercises.)
, that is implemented using the
AdjacencyLists data structure, the
,
and
algorithms each run in
time.Breadth-first search seems to have been discovered independently by Moore [52] and Lee [49] in the contexts of maze exploration and circuit routing, respectively.
Adjacency-list representations of graphs were presented by
Hopcroft and Tarjan [40] as an alternative to the (then more
common) adjacency-matrix representation. This representation, as well as
depth-first-search, played a major part in the celebrated Hopcroft-Tarjan
planarity testing algorithm
that can determine, in
time, if
a graph can be drawn, in the plane, and in such a way that no pair of
edges cross each other [41].
In the following exercises, an undirected graph is one in which, for
every
and
, the edge
is present if and only if the
edge
is present.
, is an
matrix, 
, where
,
,
,
,
and
.
be an undirected graph. We say 
is connected if,
for every pair of vertices
and
in 
, there is a path from
to
(since 
is undirected, there is also a path from
to
). Show how to test if 
is connected in
time.
be an undirected graph. A connected-component labelling
of 
partitions the vertices of 
into maximal sets, each of which
forms a connected subgraph. Show how to compute a connected component
labelling of 
in
time.
be an undirected graph. A spanning forest of 
is a
collection of trees, one per component, whose edges are edges of 
and whose vertices contain all vertices of 
. Show how to compute
a spanning forest of of 
in
time.
is strongly-connected if, for every
pair of vertices
and
in 
, there is a path from
to
. Show how to test if 
is strongly-connected in
time.
and some special vertex
, show how
to compute the length of the shortest path from
to
for every
vertex
.
code visits the nodes of a
graph in an order that is different from that of the
code.
Write a version of
that always visits nodes in exactly
the same order as
. (Hint: Just start tracing the execution
of each algorithm on some graph where
is the source of more than
1 edge.)
is a vertex that is the target
of
edges and the source of no edges.12.1 Design and implement an algorithm that tests if a graph 
, represented
as an AdjacencyMatrix, has a universal sink. Your algorithm should
run in
time.
, is also sometimes called a celebrity: Everyone in the room
recognizes
, but
doesn't recognize anyone else in the room.
![\includegraphics[scale=0.90909]{figs-python/graph-example2}](img4821.png)
