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{\ensuremath{\ensuremath{\mathit{n}}}}_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}}$ as the number of vertices, $ \ensuremath{\ensuremath{\mathit{i}}}$, of $ G$, for which there exists a path from $ \ensuremath{\ensuremath{\mathit{r}}}$ to $ \ensuremath{\ensuremath{\mathit{i}}}$. Define $ \ensuremath{\ensuremath{\ensuremath{\mathit{m}}}}_\ensuremath{\ensuremath{\ensuremath{\mathit{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, $ \ensuremath{\ensuremath{\mathit{g}}}$, that is implemented using the AdjacencyLists data structure, the $ \ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$, $ \ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ and $ \ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ algorithms each run in $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}_{\ensuremath{\ensuremath{\...
...{\ensuremath{\mathit{m}}}}_{\ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}})$ 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 $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ 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 $ \ensuremath{\ensuremath{\mathit{i}}}$ and $ \ensuremath{\ensuremath{\mathit{j}}}$, the edge $ (\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}},\ensuremath{\ensuremath{\ensuremath{\mathit{j}}}})$ is present if and only if the edge $ (\ensuremath{\ensuremath{\ensuremath{\mathit{j}}}},\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}})$ is present.

Exercise 12..1   Draw an adjacency list representation and an adjacency matrix representation of the graph in Figure 12.7.

Figure 12.7: An example graph.
\includegraphics[scale=0.90909]{figs-python/graph-example2}

Exercise 12..2   The incidence matrix representation of a graph, $ G$, is an $ \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}\times\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}}$ matrix, $ A$, where

$\displaystyle A_{i,j} = \begin{cases}
-1 & \text{if vertex $i$\ the source of ...
...if vertex $i$\ the target of edge $j$} \\
0 & \text{otherwise.}
\end{cases} $

  1. Draw the incident matrix representation of the graph in Figure 12.7.
  2. Design, analyze and implement an incidence matrix representation of a graph. Be sure to analyze the space, the cost of $ \ensuremath{\mathrm{add\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$, $ \ensuremath{\mathrm{remove\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$, $ \ensuremath{\mathrm{has\_edge}(\ensuremath{\mathit{i}},\ensuremath{\mathit{j}})}$, $ \ensuremath{\mathrm{in\_edges}(\ensuremath{\mathit{i}})}$, and $ \ensuremath{\mathrm{out\_edges}(\ensuremath{\mathit{i}})}$.

Exercise 12..3   Illustrate an execution of the $ \ensuremath{\mathrm{bfs}(G,0)}$ and $ \ensuremath{\mathrm{dfs}(G,0)}$ on the graph, $ G$, in Figure 12.7.

Exercise 12..4   Let $ G$ be an undirected graph. We say $ G$ is connected if, for every pair of vertices $ \ensuremath{\ensuremath{\mathit{i}}}$ and $ \ensuremath{\ensuremath{\mathit{j}}}$ in $ G$, there is a path from $ \ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}$ to $ \ensuremath{\ensuremath{\ensuremath{\mathit{j}}}}$ (since $ G$ is undirected, there is also a path from $ \ensuremath{\ensuremath{\mathit{j}}}$ to $ \ensuremath{\ensuremath{\mathit{i}}}$). Show how to test if $ G$ is connected in $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

Exercise 12..5   Let $ G$ be an undirected graph. A connected-component labelling of $ G$ partitions 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{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

Exercise 12..6   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{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

Exercise 12..7   We say that a graph $ G$ is strongly-connected if, for every pair of vertices $ \ensuremath{\ensuremath{\mathit{i}}}$ and $ \ensuremath{\ensuremath{\mathit{j}}}$ in $ G$, there is a path from $ \ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}$ to $ \ensuremath{\ensuremath{\ensuremath{\mathit{j}}}}$. Show how to test if $ G$ is strongly-connected in $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

Exercise 12..8   Given a graph $ G=(V,E)$ and some special vertex $ \ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}\in V$, show how to compute the length of the shortest path from $ \ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}$ to $ \ensuremath{\ensuremath{\mathit{i}}}$ for every vertex $ \ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\in V$.

Exercise 12..9   Give a (simple) example where the $ \ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ code visits the nodes of a graph in an order that is different from that of the $ \ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ code. Write a version of $ \ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ that always visits nodes in exactly the same order as $ \ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$. (Hint: Just start tracing the execution of each algorithm on some graph where $ \ensuremath{\ensuremath{\mathit{r}}}$ is the source of more than 1 edge.)

Exercise 12..10   A universal sink in a graph $ G$ is a vertex that is the target of $ \ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}-1$ edges and the source of no edges.12.1 Design and implement an algorithm that tests if a graph $ G$, represented as an AdjacencyMatrix, has a universal sink. Your algorithm should run in $ O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ time.



Footnotes

... edges.12.1
A universal sink, $ \ensuremath{\ensuremath{\mathit{v}}}$, is also sometimes called a celebrity: Everyone in the room recognizes $ \ensuremath{\ensuremath{\mathit{v}}}$, but $ \ensuremath{\ensuremath{\mathit{v}}}$ doesn't recognize anyone else in the room.
opendatastructures.org