12.4 Discussion and Exercises

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