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 $\mathtt{Graph}$, $\mathtt{g}$, that is implemented using the $\mathtt{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 [47] and Lee [44] in the contexts of maze exploration and circuit routing, respectively.

Adjacency-list representations of graphs were first popularized by Hopcroft and Tarjan [36] 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 [37].

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   Draw an adjacencly list representation and an adjacency matrix representation of the graph in Figure 12.7.

Figure 12.7: An example graph.

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

$$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 $\mathtt{addEdge(i,j)}$, $\mathtt{removeEdge(i,j)}$, $\mathtt{hasEdge(i,j)}$, $\mathtt{inEdges(i)}$, and $\mathtt{outEdges(i)}$.

Exercise 12..3   Illustrate an execution of the $\mathtt{bfs(G,0)}$ and $\mathtt{dfs(G,0)}$ on the graph, $\ensuremath{\mathtt{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 $\mathtt{i}$ and $\mathtt{j}$ in $G$, there is a path from $\ensuremath{\mathtt{i}}$ to $\ensuremath{\mathtt{j}}$ (since $G$ is undirected, there is also a path from $\mathtt{j}$ to $\mathtt{i}$). Show how to test if $G$ is connected in $O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{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{\mathtt{n}} + \ensuremath{\mathtt{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{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.

Exercise 12..7   We say that a graph $G$ is strongly-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 strongly-connected in $O(\ensuremath{\mathtt{n}} + \ensuremath{\mathtt{m}})$ time.

Exercise 12..8   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..9   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.)

Exercise 12..10   A universal sink in a graph $G$ is a vertex that is the target of $\ensuremath{\mathtt{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 $\mathtt{AdjacencyMatrix}$, has a universal sink. Your algorithm should run in $O(\ensuremath{\mathtt{n}})$ time.

Footnotes

... edges.^12.1

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