602
Graph Algorithms
The dark lines in Figure 7.13 are part of the depth-first search tree associated
with the search of Example 11, and the dark lines in Figures 7.15 and 7.16 are part
of the breadth-first search tree associated with the search of Example 12.
praCtiCe 16
a. Complete the depth-first search tree for Example 11.
b. Complete the breadth-first search tree for Example 12.
The depth-first search and breadth-first search algorithms apply equally well
to directed graphs and in the process yield a new algorithm for reachability. To
determine whether node j is reachable from node i, do a depth-first (or breadthfirst) search beginning at node i; when the algorithm terminates, check whether
node j has been visited. “All pairs” reachability, that is, which nodes are reachable from which nodes, can thus be determined by running depth-first or breadthfirst searches using each node in turn as the source node. This process would
require Θ(n * max(n, m)) work. If the graph is very sparse, in which case we have
max(n, m) = n, we would have an Θ(n
2
) algorithm for reachability. Recall that
Warshall’s algorithm (Section 7.1) was an Θ(n
3
) algorithm. The improvement
comes about because in a sparse graph, most adjacency lists will be short or empty, whereas Warshall’s algorithm processes entries in the adjacency matrix even if
those entries are 0s. But if the graph is not sparse, the number of arcs can be Θ(n
2
),
in which case Θ(n * min(n, m)) = Θ(n
3
), the same as Warshall’s algorithm. In addition, Warshall’s algorithm has the advantage of succinct implementation.
In Section 5.2 we defined a topological sort as a way to extend a partial ordering on a finite set to a total ordering. Let the partially ordered set be represented
by a directed graph. The topological sort will be achieved by counting the nodes,
so let the initial value of the count be 0. Pick a node as a source node and perform
a depth-first search from this node. Whenever the search backs up from a node for
the final time, assign that node the next counting number. When the depth-first
search algorithm terminates, pick an unvisited node (if one exists) to be the source
for another depth-first search, and continue to increment the counting number.
Continue this process until there are no unvisited nodes left in the graph. A topological sort results by ordering the nodes in the reverse order of their counting
number. This process for topological sorting works because we assign the counting number when we back up from a node for the final time. Its counting number
will then be higher than the numbers of all the nodes reachable from it, that is, all
the nodes of which it is a predecessor in the partial ordering,
example 13
Figure 7.17a is a directed graph that represents a partial ordering. Choosing d
(arbitrarily) as the source node and performing a depth-first search, we visit e and
f, at which point we must back up. Node f is assigned the counting number 1, but
we are not yet done with e, because we can go on to visit g. Backing up from g,
g is assigned the counting number 2. At this point we back up from e for the final
time and assign e the number 3 and then d the number 4. We choose a as the source
node for another search. We visit node c and then must back up, so c and a are assigned the numbers 5 and 6, respectively. Beginning with b as a source node, there
■
Graph Algorithms
The dark lines in Figure 7.13 are part of the depth-first search tree associated
with the search of Example 11, and the dark lines in Figures 7.15 and 7.16 are part
of the breadth-first search tree associated with the search of Example 12.
praCtiCe 16
a. Complete the depth-first search tree for Example 11.
b. Complete the breadth-first search tree for Example 12.
The depth-first search and breadth-first search algorithms apply equally well
to directed graphs and in the process yield a new algorithm for reachability. To
determine whether node j is reachable from node i, do a depth-first (or breadthfirst) search beginning at node i; when the algorithm terminates, check whether
node j has been visited. “All pairs” reachability, that is, which nodes are reachable from which nodes, can thus be determined by running depth-first or breadthfirst searches using each node in turn as the source node. This process would
require Θ(n * max(n, m)) work. If the graph is very sparse, in which case we have
max(n, m) = n, we would have an Θ(n
2
) algorithm for reachability. Recall that
Warshall’s algorithm (Section 7.1) was an Θ(n
3
) algorithm. The improvement
comes about because in a sparse graph, most adjacency lists will be short or empty, whereas Warshall’s algorithm processes entries in the adjacency matrix even if
those entries are 0s. But if the graph is not sparse, the number of arcs can be Θ(n
2
),
in which case Θ(n * min(n, m)) = Θ(n
3
), the same as Warshall’s algorithm. In addition, Warshall’s algorithm has the advantage of succinct implementation.
In Section 5.2 we defined a topological sort as a way to extend a partial ordering on a finite set to a total ordering. Let the partially ordered set be represented
by a directed graph. The topological sort will be achieved by counting the nodes,
so let the initial value of the count be 0. Pick a node as a source node and perform
a depth-first search from this node. Whenever the search backs up from a node for
the final time, assign that node the next counting number. When the depth-first
search algorithm terminates, pick an unvisited node (if one exists) to be the source
for another depth-first search, and continue to increment the counting number.
Continue this process until there are no unvisited nodes left in the graph. A topological sort results by ordering the nodes in the reverse order of their counting
number. This process for topological sorting works because we assign the counting number when we back up from a node for the final time. Its counting number
will then be higher than the numbers of all the nodes reachable from it, that is, all
the nodes of which it is a predecessor in the partial ordering,
example 13
Figure 7.17a is a directed graph that represents a partial ordering. Choosing d
(arbitrarily) as the source node and performing a depth-first search, we visit e and
f, at which point we must back up. Node f is assigned the counting number 1, but
we are not yet done with e, because we can go on to visit g. Backing up from g,
g is assigned the counting number 2. At this point we back up from e for the final
time and assign e the number 3 and then d the number 4. We choose a as the source
node for another search. We visit node c and then must back up, so c and a are assigned the numbers 5 and 6, respectively. Beginning with b as a source node, there
■