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
$ \ensuremath{\mathtt{n}}_{\ensuremath{\mathtt{r}}}$ as the number of vertices,
$ \mathtt{i}$,
of $ G$, for which there exists a path from
$ \mathtt{r}$ to
$ \mathtt{i}$. Define
$ \ensuremath{\mathtt{m}}_\ensuremath{\mathtt{r}}$
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.)
Theorem 12..5
When given as input a Graph,
$ \mathtt{g}$, that is implemented using the
AdjacencyLists data structure, the
$ \mathtt{bfs(g,r)}$,
$ \mathtt{dfs(g,r)}$ and
$ \mathtt{dfs2(g,r)}$
algorithms each run in
$ O(\ensuremath{\mathtt{n}}_{\ensuremath{\mathtt{r}}}+\ensuremath{\mathtt{m}}_{\ensuremath{\mathtt{r}}})$ time.
Breadth-first search seems to have been discovered independently by
Moore [43] and Lee [42] in the contexts of maze exploration
and circuit routing, respectively.
Adjacency-list representations of graphs were first popularized by
Hopcroft and Tarjan [34] as an alternative to the (then more
common) adjacency-matrix representation. This representation, and
depth-first-search, played a major part in the celebrated Hopcroft-Tarjan
planarity testing algorithm that can determine, in
$ O(\ensuremath{\mathtt{n}})$ time, if
a graph can be drawn, in the plane, and in such a way that no pair of
edges cross each other [35].
In the following exercises, an undirected graph is one in which, for
every
$ \mathtt{i}$ and
$ \mathtt{j}$, the edge
$ (\ensuremath{\mathtt{i}},\ensuremath{\mathtt{j}})$ is present if and only if the
edge
$ (\ensuremath{\mathtt{j}},\ensuremath{\mathtt{i}})$ is present.
Exercise 12..1
Let $ G$ be an undirected graph. We say $ G$ is connected if, for
every pair of vertices
$ \mathtt{i}$ and
$ \mathtt{j}$ in $ G$, there is a path from
$ \ensuremath{\mathtt{i}}$
to
$ \ensuremath{\mathtt{j}}$. Show how to test if $ G$ is connected in
$ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.
Exercise 12..2
We say $ G$ is connected if, for
every pair of vertices
$ \mathtt{i}$ and
$ \mathtt{j}$ in $ G$, there is a path from
$ \ensuremath{\mathtt{i}}$
to
$ \ensuremath{\mathtt{j}}$. Show how to test if $ G$ is connected in
$ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.
Exercise 12..3
Let $ G$ be an undirected graph. A connected-component labelling
of $ G$ partitions to the vertices of $ G$ into maximal sets, each of
which forms a connected subgraph. Show how to compute a connected
component labelling of $ G$ in
$ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.
Exercise 12..4
Let $ G$ be an undirected graph. A spanning forest of $ G$ is a
collection of trees, one per component, whose edges are edges of $ G$
and whose vertices contain all vertices of $ G$. Show how to compute
a spanning forest of of $ G$ in
$ O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.
Exercise 12..5
Given a graph $ G=(V,E)$ and some special vertex
$ \ensuremath{\mathtt{r}}\in V$, show how
to compute the length of the shortest path from
$ \ensuremath{\mathtt{r}}$ to
$ \mathtt{i}$ for every
vertex
$ \ensuremath{\mathtt{i}}\in V$.
Exercise 12..6
Give a (simple) example where the
$ \mathtt{dfs(g,r)}$ code visits the nodes of a
graph in an order that is different from that of the
$ \mathtt{dfs2(g,r)}$ code.
Write a version of
$ \mathtt{dfs2(g,r)}$ that always visits nodes in exactly
the same order as
$ \mathtt{dfs(g,r)}$. (Hint: Just start tracing the execution
of each algorithm on some graph where
$ \mathtt{r}$ is the source of more than
1 edge.)
opendatastructures.org