160 Decrease-and-Conquer

A few other examples of decrease-by-a-constant-factor algorithms are given

in Section 5.5 and its exercises. Such algorithms are so efficient, however, that
there are few examples of this kind.
Finally, in the val'iable-size-decrease variety of decrease-and-conquer, a size
reduction pattern varies from one iteration of an algorithm to another. Euclid's
algorithm for computing the greatest common divisor provides a good example
of such a situation. Recall that this algorithm is based on the formula

gcd(m, n) = gcd(11, m mod 11).

Though the arguments on the right-hand side are always smaller than those on the
left-hand side (at least starting with the second iteration of the algorithm), they
are smaller neither by a constant nor by a constant factor. A few other examples
of such algorithms appear in Section 5.6.

5.1 Insertion Sort

In this section, we consider an application of the decrease-by-one technique to
sorting an array A[0 .. 11- 1]. Following the technique's idea, we assume that tbe
smaller problem of sorting the array A[O .. n- 2] has already been solved to give
us a sorted array of size 11 - 1: A[O] :<' ... :<'A [11 - 2]. How can we take advantage
of this solution to the smaller problem to get a solution to the original problem
by taking into account the element A[n -1]? Obviously, all we need is to find an
appropriate position for A[n - 1] among the sorted elements and insert it there.
There are three reasonable alternatives for doing this. First, we can scan the
sorted subarray from left to right until the first element greater than or equal
to A[11 -1] is encountered and then insert A[11 -1] right before that element.
Second, we can scan the sorted subarray from right to left until the first element
smaller than or equal to A[n -1] is encountered and then insert A[n -1] right
after that element. These two alternatives are essentially equivalent; usually, it is
the second one that is implemented in practice because it is better for sorted and
almost-sorted arrays (whf\). The resulting algorithm is called straight insertion
sort or simply insertion sort. The third alternative is to use binary search to find an
appropriate position for A [n - 1] in the sorted portion of the array. The resulting
algorithm is called binary insertion sort. We ask you to implement this idea and
investigate the efficiency of binary insertion sort in the exercises to this section.
Though insertion sort is clearly based on a recursive idea, it is more efficient
to implement this algorithm bottom up, i.e., iteratively. As shown in Figure 5.3,
starting with A[1] and ending with A[n - 1], A[i] is inserted in its appropriate place
among the first i elements of the array that have been already sorted (but, unlike
selection sort, are generally not in their final positions).
Here is a pseudocode of this algorithm.
 5.1 Insertion Sort 161

A[O] ::0 ... ::0 A[j] < A[j + 1] ::0 ... ::0 A[i -1] I A[i] ... A[n -1]
smaller than or equal to A[i] greater than A[i]

FIGURE 5.3 Iteration of insertion sort: A[i] is inserted in its proper position among the
preceding elements previously sorted.

ALGORITHM InsertionSort(A[O .. n - 1])

//Sorts a given array by insertion sort
//lnput: An array A[O .. n- 1] of n orderable elements
//Output: Array A[O .. n - 1] sorted in nondecreasing order
for i <--- 1 to n - 1 do (\
v <--- A[i]
j<---i-1
while j :>: 0 and A[j] > v do '2

A[j + 1] <--- A[j]

j<---j-1
A[j+1]<-v

The operation of the algorithm is illustrated in Figure 5.4.

c\""" The basic operation of the algorithm is the key comparison A[j] > v. (Why
)not j :>: 0? Because it will almost certainly be faster than the former in an actual
~'<~r 1 computer implementation. Moreover, it is not germane to the algorithm: a better
implementation with a sentinel-see Problem 5 in the exercises-eliminates it
,.-,--~-----------
altogether.)
The number of key comparisons in this algorithm obviously depends on the
nature of the input. In the worst case, A[j] > v is executed the largest number
of times, i.e., for every j = i - 1, ... , 0. Since v = A[i], it happens if and only if

89 I 45 68 90 29 34 17
45 89 I 68 90 29 34 17
45 68 89 I 90 29 34 17
45 68 89 90 I 29 34 17
29 45 68 89 90 I 34 17
29 34 45 68 89 90 I 17
17 29 34 45 68 89 90

FIGURE 5.4 Example of sorting with insertion sort. A vertical bar separates the sorted
part of the array from the remaining elements; the element being inserted
is in bold.
162 Decrease-and-Conquer

A[j] > A[i] for j = i- 1, ... , 0. (Note that we are using the fact that on the ith
iteration of insertion sort all the elements preceding A[i] are the first i elements in
the input, albeit in the sorted order.) Thus, for the worst-case input, we get A[O] >
A[1] (fori= 1), A[1] > A[2] (fori= 2), ... , A[n- 2] > A[n -1] (fori= n -1).
In other words, the worst-case input is an array of strictly decreasing values. The
number of key comparisons for such an input is

n-1 i-l n-1 ( )

'\''\' '\'· n- 1 n
Cw 0 ,-,(n) = L... L...1 = L... l = E E>(n 2 ).
i=l j=O i=l
2

Thus, in the wo~st case, insertion sort makes exactly the same number of compar-
isons as selection sort (see Section 3.1).
In the best case, the comparison A[j] > v is executed only once on every
iteration of the outer loop. It happens if and only if A[i - 1]::: A[i] for every i =
1, ... , n - 1, i.e., if the input array is already sorted in ascending order. (Though
it "makes sense" that the best case of an algorithm happens when the problem
is already solved, it is not always the case: recall our discussion of quicksort in
Chapter 4.) Thus, for sorted arrays, the number of key comparisons is

n-1
ch,,,,(n) = L 1 = n- 1 E E>(n).
i=l

This very good performance in the best case of sorted arrays is not very useful
by itself, because we cannot expect such convenient inputs. However, almost-
sorted files arise in a variety of applications, and insertion sort preserves its
excellent performance on such inputs. For example, while sorting an array by
quicksort, we can stop the algorithm's iterations after subarrays become smaller
than some predefined size (say, 10 elements). By that time, the entire array is
almost sorted and we can finish the job by applying insertion sort to it. This
modification typically decreases the total running time of quicksort by about 10%.
t c\.cc== ... A rigorous analysis of the algorithm's average-case efficiency is based on
investigating the number of element pairs that are out of order (see Problem 8).
It shows that on randomly ordered arrays, insertion sort makes on average half as
many comparisons as on decreasing arrays, i.e.,

This twice-as-fast average-case performance coupled with an excellent efficiency

on almost-sorted arrays makes insertion sort stand out among its principal com-
petitors among elementary sorting algorithms, selection sort and bubble sort. In
addition, its extension named shellsort, after its inventor D. L. Shell [She59], gives
us an even better algorithm for sorting moderately large files (see Problem 10).
 5.1 Insertion Sort 163

-----Exercises 5.1 - - - - - - - - - - - - - - - -
1. Ferrying soldiers A detachment of n soldiers must cross a wide and deep
river with no bridge in sight. They notice two 12-year-old boys playing in a
rowboat by the shore. The boat is so tiny, however, that it can only hold two
boys or one soldier. How can the soldiers get across the river and leave the
boys in joint possession of the boat? How many times need the boat pass from
shore to shore?
2. Alternating glasses There are 2n glasses standing next to each other in a row,
the first n of them filled with a soda drink, while the remaining n glasses are
empty. Make the glasses alternate in a filled-empty-filled-empty pattern in the
minimum number of glass moves. (Gar78], p. 7

0000 O'i/0 O'i/0

3. Design a decrease-by-one algorithm for generating the power set of a set of n
elements. (The power set of a set S is the set of all the subsets of S, including
the empty set and S itself.)
4. Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
5. a. What sentinel should be put before the first element of an array being
sorted to avoid checking the in-bound condition j 2: 0 on each iteration
of the inner loop of insertion sort?
b. Will the version with the sentinel be in the same efficiency class as the
original version?
6. Is it possible to implement insertion sort for sorting linked lists? Will it have
the same O(n 2 ) efficiency as the array version?
7. Consider the following version of insertion sort.

ALGORITHM InsertSort2(A[O .. n - 1])

fori <--lton-1do
j<--i-1
while j 2:0 and A(j] > A[j + 1] do
swap( A(}], A(j + 1])
j<--j-1

What is its time efficiency? How is it compared to that of the version given in
the text?
8. Let A[O .. n - 1] be an array of n sortable elements. (For simplicity, you can
assume that all the elements are distinct.) A pair (A(i], A[j]) is called an
inversion if i < j and A[i] > A[j].
164 Decrease-and-Conquer

a. What arrays of size n have the largest number of inversions and what is this
number? Answer the same questions for the smallest number of inversions.
b. Show that the average-case number of key comparisons in insertion sort is
given by the formula

9. Binary insertion sort uses binary search to find an appropriate position to

insert A[i] among the previously sorted A[O] :S ... :s A[i - 1]. Determine the
worst-case efficiency class of this algorithm.
10. Shellsort (more accurately Shell's sort) is an important sorting algorithm that
works by applying insertion sort to each of several interleaving sublists of a
given list. On each pass through the list, the sublists in question are formed
by stepping through the list with an increment h, taken from some predefined
decreasing sequence of step sizes, h1 > ... >hi > ... > 1, which must end with
1. (The algorithm works for any such sequence, though some sequences are
known to yield a better efficiency than others. For example, the sequence 1,
4, 13, 40, 121, ... , used, of course, in reverse, is known to be among the best
for this purpose.)
a. Apply shellsort to the list
S, H, E, L, L, S, 0, R, T, I, S, U, S, E, F, U, L

b. Is shellsort a stable sorting algorithm?

c. Implement shellsort, straight insertion sort, binary insertion sort, merge-
sort, and quicksort in the language of your choice and compare their per-
formance on random arrays of sizes 102 , 103, 104 , and 105 as well as on
increasing and decreasing arrays of these sizes.

!5.2 Depth-First Search and Breadth-First Search

In the next two sections of this chapter, we deal with very important graph al-
gorithms that can be viewed as applications of the decrease-by-one technique.
We assume familiarity with the notion of a graph, its main varieties (undirected,
directed, and weighted graphs), the two principal representations of a graph (ad-
jacency matrix and adjacency lists), and such notions as graph connectivity and
acyclicity. If needed, a brief review of this material can be found in Section 1.4.
As pointed out in Section 1.3, graphs are interesting structures with a wide
variety of applications. Many graph algorithms require processing vertices or
edges of a graph in a systematic fashion. There are two principal algorithms for
doing such traversals: depth-first search (DFS) and breadth-first search (BFS). In
 5.2 Depth-First Search and Breadth-First Search 165

addition to doing their main job of visiting vertices and traversing edges of a graph.
these algorithms have proved to be very useful in investigating several important
properties of a graph.

Depth-First Search
Depth-first search starts visiting vertices of a graph at an arbitrary vertex by mark-
ing it as having been visited. On each iteration, the algorithm proceeds to an
unvisited vertex that is adjacent to the one it is currently in. (If there are sev-
eral such vertices. a tie can be resolved arbitrarily. As a practical matter, which
of the adjacent unvisited candidates is chosen is dictated by the data structure
representing the graph. In our examples, we will always break ties by the alpha-
betical order of the vertices.) This process continues until a dead end-a vertex
with no adjacent unvisited vertices-is encountered. At a dead end, the algorithm
backs up one edge to the vertex it came from and tries to continue visiting un-
visited vertices from there. The algorithm eventually halts after backing up to
the starting vertex, with the latter being a dead end. By then, all the vertices in
the same connected component as the starting vertex have been visited. If unvis-
ited vertices still remain, the depth-first search must be restarted at any one of
them.
It is convenient to use a stack to trace the operation of depth-first search. We
push a vertex onto the stack when the vertex is reached for the first time (i.e., the
visit of the vertex starts), and we pop a vertex off the stack when it becomes a
dead end (i.e., the visit of the vertex ends).
It is also very useful to accompany a depth-first search traversal by construct-
ing the so-called depth-first search forest. The traversal's starting vertex serves
as the root of the first tree in such a forest. Whenever a new unvisited vertex is
reached for the first time, it is attached as a child to the vertex from which it is being
reached. Such an edge is called a tree edge because the set of all such edges forms
a forest. The algorithm may also encounter an edge leading to a previously visited
vertex other than its immediate predecessor (i.e., its parent in the tree). Such an
edge is called a back edge because it connects a vertex to its ancestor, other than
the parent, in the depth-first search forest. Figure 5.5 provides an example of a
depth-first search traversal, with the traversal's stack and corresponding depth-
first search forest shown as well.
Here is a pseudocode of the depth-first search.

ALGORITHM DFS(G)
//Implements a depth-first search traversal of a given graph
//Input: Graph G = (V, E)
//Output: Graph G with its vertices marked with consecutive integers
//in the order they've been first encountered by the DFS traversal
 {.,

;tri
rli
I
166 Decrease-and-Conquer

g)-----------1 h
ee. 2
b5, 3 ho.7
d3 , 1 f4,4 ig,a
c2. 5 ha. 9
8 1,6 97.1o

(a) (b) (c)

FIGURE 5.5 Example of a DFS traversal. (a) Graph. (b) Traversal's stack (the first subscript
number indicates the order in which a vertex was visited, i.e., pushed onto
the stack; the second one indicates the order in which it became a dead-
end, i.e., popped off the stack). (c) DFS forest (with the tree edges shown
with solid lines and the back edges shown with dashed lines).

mark each vertex in V with 0 as a mark of being "unvisited"

count+--- 0
for each vertex v in V do
if v is marked with 0
dfs(v)

dfs(v)
//visits recursively all the unvisited vertices connected to vertex v hy a path
//and numbers them in the order they are encountered
//via global variable count
count +---count + 1; mark v with count
for each vertex w in V adjacent to v do
if w is marked with 0
df<(w)

The brevity of the DFS pseudocode and the ease with which it can be per-
formed by hand may create a wrong impression about the level of sophistication
of this algorithm. To appreciate its true power and depth, you should trace the
algorithm's action by looking not at a graph's diagram but at its adjacency matrix
or adjacency lists. (Try it for the graph in Figure 5.5 or a smaller example.)
How efficient is depth-first search? It is not difficult to see that this algorithm
is, in fact, quite efficient since it takes just the time proportional to the size of the
data structure used for representing the graph in question. Thus, for the adjacency
matrix representation, the traversal's time is in 8(1VI 2 ), and for the adjacency
 5.2 Depth-First Search and Breadth-First Search 167

list representation, it is in El(IVI +lEI) where lVI and lEI are the number of the
graph's vertices and edges, respectively.
A DFS forest, which is obtained as a by-product of a DFS traversal, deserves a
few comments, too. To begin with, it is not actually a forest. Rather, we can look at
it as the given graph with its edges classified by the DFS traversal into two disjoint
classes: tree edges and back edges. (No other types are possible for a DFS forest
of an undirected graph.) Again, tree edges are edges used by the DFS traversal to
reach previously unvisited vertices. If we consider only the edges in this class, we
will indeed get a forest. Back edges connect vertices to previously visited vertices
other than their immediate predecessors in the traversal. They connect vertices to
their ancestors in the forest other than their parents.
A DFS traversal itself and the forest-like representation of a graph it provides
have proved to be extremely helpful for the development of efficient algorithms
for checking many important properties of graphs1 Note that the DFS yields two
orderings of vertices: the order in which the vertices are reached for the first
time (pushed onto the stack) and the order in which the vertices become dead
ends (popped off the stack). These orders are qualitatively different, and various
applications can take advantage of either of them.
Important elementary applications of DFS include checking connectivity and
checking acyclicity of a graph. Since DFS halts after visiting all the vertices con-
nected by a path to the starting vertex, checking a graph's connectivity can be done
as follows. Start a DFS traversal at an arbitrary vertex and check, after the algo·
rithm halts, whether all the graph's vertices will have been visited. If they have,
the graph is connected; otherwise, it is not connected. More generally, we can use
DFS for identifying connected components of a graph (how?).
As for checking for a cycle presence in a graph, we can take advantage of the
graph's representation in the form of a DFS forest. If the latter does not have back
edges, the graph is clearly acyclic. If there is a back edge from some vertex u to its
ancestor v (e.g., the back edge from d to a in Figure 5.5c), the graph has a cycle
that comprises the path from v to u via a sequence of tree edges in the DFS forest
followed by the back edge from u to v.
You will find a few other applications of DFS later in the book, although more
sophisticated applications, such as finding articulation points of a graph, are not
included. (A vertex of a connected graph is said to be its articulation point if its
removal with all edges incident to it breaks the graph into disjoint pieces.)

Breadth-First Search
If depth-first search is a traversal for the brave (the algorithm goes as far from
"home" as it can), breadth-first search is a traversal for the cautious. It proceeds in

1. The discovery of several such applications was an important breakthrough achieved by the two
American computer scientists John Hopcroft and Robert Tarjan in the 1970s. For this and other
contributions, they subsequently won the Turing Award-the most important prize given in theoretical
computer science [Hop87, Tar87].
168 Decrease-and-Conquer

g h

~ 4 a1 c2 d3 e4 fs b5 j
97 hsjg iw

(a) (b) (c)

FIGURE 5.6 Example of a BFS traversal. (a) Graph. (b) Traversal's queue, with the
numbers indicating the order in which the vertices were visited, i.e., added
to (or removed from) the queue. (c) BFS forest (with the tree edges shown
with solid lines and the cross edges shown with dotted lines).

a concentric manner by visiting first all the vertices that are adjacent to a starting
vertex, then all unvisited vertices two edges apart from it, and so on, until all
the vertices in the same connected component as the starting vertex are visited.
If there still remain unvisited vertices, the algorithm has to be restarted at an
arbitrary vertex of another connected component of the graph.
It is convenient to use a queue (note the difference from depth-first search!)
to trace the operation of breadth-first search. The queue is initialized with the
traversal's starting vertex, which is marked as visited. On each iteration, the
algorithm identifies all unvisited vertices that are adjacent to the front vertex,
marks them as visited, and adds them to the queue; after that, the front vertex is
removed from the queue.
Similarly to a DFS traversal, it is useful to accompany a BFS traversal by con-
structing the so-called breadth-first search forest. The traversal's starting vertex
serves as the root of the first tree in such a forest. Whenever a new unvisited vertex
is reached for the first time, the vertex is attached as a child to the vertex it is being
reached from with an edge called a tree edge. If an edge leading to a previously
visited vertex other than its immediate predecessor (i.e., its parent in the tree) is
encountered, the edge is noted as a cross edge. Figure 5.6 provides an example
of a breadth-first search traversal, with the traversal's queue and corresponding
breadth-first search forest shown.
Here is a pseudocode of the breadth-first search.

ALGORITHM BFS(G)
//Implements a breadth-first search traversal of a given graph
//Input: Graph G = (V, E)
//Output: Graph G with its vertices marked with consecutive integers
//in the order they have been visited by the BFS traversal
 5.2 Depth-First Search and Breadth-First Search 169

mark each vertex in V with 0 as a mark of being "unvisited"

count +- 0
for each vertex v in V do
if v is marked with 0
bfs(v)

bfs(v)
//visits all the unvisited vertices connected to vertex v by a path
//and assigns them the numbers in the order they are visited
//via global variable count
count +-count + 1; mark v with count and initialize a queue with v
while the queue is not empty do
for each vertex w in V adjacent to the front vertex do
if w is marked with 0
count +-- count + 1; mark w with count
add w to the queue
remove the front vertex from the queue

Breadth-first search has the same efficiency as depth-first search: it is in

8(1VI 2 ) for the adjacency matrix representation and in 8(1VI +lEI) for the adja-
cency list representation. Unlike depth-first search, it yields a single ordering of
vertices because the queue is a FIFO (first-in first-out) structure and hence the
order in which vertices are added to the queue is the same order in which they
are removed from it. As to the structure of a BFS forest of an undirected graph,
it can also have two kinds of edges: tree edges and cross edges. Tree edges are the
ones used to reach previously unvisited vertices. Cross edges connect vertices to
those visited before, but, unlike back edges in a DFS tree, they connect vertices
either on the same or adjacent levels of a BFS tree.
Finally, BFS can be used to check connectivity and acyclicity of a graph,
essentially in the same manner as DFS can. It is not applicable, however, for
several less straightforward applications such as finding articulation points. On the
other hand, it can be helpful in some situations where DFS cannot. For example,
BFS can be used for finding a path with the fewest number of edges between two
given vertices. We start a BFS traversal at one of the two vertices given and stop
it as soon as the other vertex is reached. The simple path from the root of the BFS
tree to the second vertex is the path sought. For example, path a-b-e-g in the
graph in Figure 5.7 has the fewest number of edges among all the paths between
vertices a and g. Although the correctness of this application appears to stem
immediately from the way BFS operates, a mathematical proof of its validity is
not quite elementary (see, e.g., [CarOl]).
Table 5.1 summarizes the main facts about depth-first search and breadth-first
search.
r
.
.
170 Decrease-and-Conquer

b e

c f

d g

(a) (b)

FIGURE 5.7 Illustration of the BFS-based algorithm for finding a minimum-edge path.
(a) Graph. (b) Part of its BFS tree that identifies the minimum-edge path
from a to g.

TABLE 5.1 Main facts about depth-first search IDFS) and breadth-first search IBFS)

DFS BFS

Data structure stack queue

No. of vertex orderings 2 orderings 1 ordering
Edge types (undirected graphs) tree and back tree and cross
edges edges
Applications connectivity, connectivity,
acyclicity, acyclicity,
articulation minimum-edge
points paths
Efficiency for adjacent matrix 2
El(IV 11 E>(IV 2 11
Efficiency for adjacent lists E>IIVI +IE II E>IIVI +)E))

-----Exercises 5 . 2 - - - - - - - - - - - - - - - -
1. Consider the following graph.
 5.2 Depth-First Search and Breadth-First Search 171

a. Write down the adjacency matrix and adjacency lists specifying this graph.
(Assume that the matrix rows and columns and vertices in the adjacency
lists follow in the alphabetical order of the vertex labels.)
b. Starting at vertex a and resolving ties by the vertex alphabetical order,
traverse the graph by depth-first search and construct the corresponding
depth-first search tree. Give the order in which the vertices were reached
for the first time (pushed onto the traversal stack) and the order in which
the vertices became dead ends (popped off the stack).

2. If we define sparse graphs as graphs for which lEI E O(IVI), which implemen-
tation of DFS will have a better time efficiency for such graphs, the one that
uses the adjacency matrix or the one that uses the adjacency lists?

3. Let G be a graph with n vertices and m edges.

a. True or false: All its DFS forests (for traversals starting at different ver-
tices) will have the same number of trees?
b. True or false: All its DFS forests will have the same number of tree edges
and the same number of back edges?

4. Traverse the graph of Problem 1 by breadth-first search and construct the

corresponding breadth-first search tree. Start the traversal at vertex a and
resolve ties by the vertex alphabetical order.

5. Prove that a cross edge in a BFS tree of an undirected graph can connect
vertices only on either the same level or on two adjacent levels of a BFS tree.

6. a. Explain how one can check a graph's acyclicity by using breadth-first

search.
b. Does either of the two traversals-DFS or BPS-always find a cycle faster
than the other? If you answer yes, indicate which of them is better and
explain why it is the case; if you answer no, give two examples supporting
your answer.

7. Explain how one can identify connected components of a graph by using

a. a depth-first search.
b. a breadth-first search.

8. A graph is said to be bipartite if all its vertices can be partitioned into two
disjoint subsets X and Y so that every edge connects a vertex in X with a vertex
in Y. (One can also say that a graph is bipartite if its vertices can be colored in
two colors so that every edge has its vertices colored in different colors; such
graphs are also called 2-colorable). For example, graph (i) is bipartite while
graph (ii) is not.
 P:(

Iii!
I!! r!
172 Decrease-and-Conquer

~
&4
(i) (ii)

a. Design a DFS-based algorithm for checking whether a graph is bipartite.

b. Design a BFS-based algorithm for checking whether a graph is bipartite.
9. Write a program that, for a given graph, outputs
a. vertices of each connected component;
b. its cycle or a message that the graph is acyclic.
10. One can model a maze by having a vertex for a starting point, a finishing point,
dead ends, and all the points in the maze where more than one path can be
taken, and then connecting the vertices according to the paths in the maze.
a. Construct such a graph for the following maze.

b. Which traversal-DFS or BFS-would you use if you found yourself in a

maze and why?

5.3 Topological Sorting

In this section, we discuss an important problem for directed graphs. Before we
pose this problem though, let us review a few basic facts about directed graphs
themselves. A directed graph, or digraph for short, is a graph with directions
specified for all its edges (Figure 5.8a is an example). The adjacency matrix and
adjacency lists are still two principal means of representing a digraph. There are
only two notable differences between undirected and directed graphs in repre-
senting them: (1) the adjacency matrix of a directed graph does not have to be
 5.3 Topological Sorting 173

i
//,/~

(a) (b)

FIGURE 5.8 (a) Digraph. (b) DFS forest of the digraph for the DFS traversal started at a.

symmetric; (2) an edge in a directed graph has just one (not two) corresponding
nodes in the digraph's adjacency lists.
Depth-first search and breadth-first search are principal traversal algorithms
for traversing digraphs, but the structure of corresponding forests can be more
complex. Thus, even for the simple example in Figure 5.8a, the depth-first search
forest (Figure 5.8b) exhibits all four types of edges possible in a DFS forest of
a directed graph: tree edges (ab, he, de), back edges (ba) from vertices to their
ancestors, forward edges (ac) from vertices to their descendants in the tree other
than their children, and cross edges (de), which are none of the aforementioned
types.
Note that a back edge in a DFS forest of a directed graph can connect a vertex
to its parent. Whether or not it is the case, the presence of a back edge indicates
that the digraph has a directed cycle. (A directed cycle in a digraph is a sequence
of three or more of its vertices that starts and ends with the same vertex and in
which every vertex is connected to its inllllediate predecessor by an edge directed
from the predecessor to the successor.) Conversely, if a DFS forest of a digraph
has no back edges, the digraph is a dag, an acronym for directed acyclic graph.
Directions on a graph's edges lead to new questions about the graph that are
either meaningless or trivial for undirected graphs. In this section, we discuss one
such problem. As a motivating example, consider a set of five required courses
{Cl, C2, C3, C4, C5) a part-time student has to take in some degree program. The
courses can be taken in any order as long as the following course prerequisites are
met: Cl and C2 have no prerequisites, C3 requires C1 and C2, C4 requires C3, and
C5 requires C3 and C4. The student can take only one course per term. In which
order should the student take the courses?
The situation can be modeled by a digraph in which vertices represent courses
and directed edges indicate prerequisite requirements (Figure 5.9). In terms of this
digraph, the question is whether we can list its vertices in such an order that for
every edge in the graph, the vertex where the edge starts is listed before the vertex
 T
174 Decrease-and-Conquer

C1

C3

C2

FIGURE 5.9 Digraph representing the prerequisite structure of five courses

where the edge ends. (Can you find such an ordering of this digraph's vertices?)
This problem is called topological sorting. It can be posed for an arbitrary di-
graph, but it is easy to see that the problem cannot have a solution if a digraph
has a directed cycle. Thus, for topological sorting to be possible, a digraph must
be a dag. It turns out that being a dag is not only necessary but also sufficient for
topological sorting to be possible; i.e., if a digraph has no cycles, the topological
sorting problem for it has a solution. Moreover, there are two efficient algorithms
that both verify whether a digraph is a dag and, if it is, produce an ordering of
vertices that solves the topological sorting problem.
The first algorithm is a simple application of depth-flrst search: perform a DFS
traversal and note the order in which vertices become dead ends (i.e., are popped
off the traversal stack). Reversing this order yields a solution to the topological
sorting problem, provided, of course, no back edge has been encountered during
the traversal. If a back edge has been encountered, the digraph is not a dag, and
topological sorting of its vertices is impossible.
Why does the algorithm work? When a vertex v is popped off a DFS stack,
no vertex u with an edge from u to v can be among the vertices popped off before
v. (Otherwise, (u, v) would have been a back edge.) Hence, any such vertex u will
be listed after v in the popped-off order list, and before v in the reversed list.
Figure 5.10 illustrates an application of this algorithm to the digraph in Fig-
ure 5.9. Note that in Figure 5.10c, we have drawn the edges of the digraph, and
they all point from left to right as the problem's statement requires. It is a con-

C1 The popping-off order:

C5 1
C3 C42 C5, C4, C3, C1, C2
C3 3 The topologically sorted list:
C2 C14 C2 5 C2 C1--+C3->-C4_,.C5
~~
(a) (b) (c)

FIGURE 5.10 (a) Digraph for which the topological sorting problem needs to be solved.
(b) DFS traversal stack with the subscript numbers indicating the popping-
off order. (c) Solution to the problem.
 --,

5.3 Topological Sorting 175

C1
delete C1 delete C2
C3

C2 C2

delete C3 y delete C4 delete C5

~
The solution obtained is C1, C2, C3, C4, C5

FIGURE 5.11 Illustration of the source-removal algorithm for the topological sorting
problem. On each iteration, a vertex with no incoming edges is deleted
from the digraph.

venient way to check visually the correctness of a solution to an instance of the

topological sorting problem.
The second algorithm is based on a direct implementation of the decrease (by
one )-and-conquer technique: repeatedly, identify in a remaining digraph a source,
which is a vertex with no incoming edges, and delete it along with all the edges
outgoing from it. (If there are several sources, break the tie arbitrarily. If there is
none, stop because the problem cannot be solved-see Problem 6a.) The order in
which the vertices are deleted yields a solution to the topological sorting problem.
The application of this algorithm to the same digraph representing the five courses
is given in Figure 5.11.
Note that the solution obtained by the source-removal algoritlun is different
from the one obtained by the DFS-based algorithm. Both of them are correct, of
course; the topological sorting problem may have several alternative solutions.
The tiny size of the example we used might create a wrong impression about
the topological sorting problem. But imagine a large project-e.g., in construction
or research-that involves thousands of interrelated tasks with known prerequi-
sites. The first thing you should do in such a situation is to make sure that the set
of given prereqnisites is not contradictory. The convenient way of doing this is
to solve the topological sorting problem for the project's digraph. Only then can
you start thinking about scheduling your tasks to, say, minimize the total com-
pletion time of the project. This would require, of course, other algorithms that
you can find in general books on operations research or in special ones on so-
called CPM (Critical Path Method) and PERT (Program Evaluation and Review
Technique) methodologies.
 T,
176 Decrease-and-Conquer

------Exercises 5 . 3 - - - - - - - - - - - - - - - - -
1. Apply the DFS-based algorithm to solve the topological sorting problem for
the following digraphs.
}--.{d

(a) (b)

2. a. Prove that the topological sorting problem has a solution for a digraph if
and only if it is a dag.
b. For a digraph with n vertices, what is the largest number of distinct solutions
the topological sorting problem can have?
3. a. What is the time efficiency of the DFS-based algorithm for topological
sorting?
b. How can one modify the DFS-based algorithm to avoid reversing the
vertex ordering generated by DFS? ·
4. Can one use the order in which vertices are pushed onto the DFS stack
(instead of the order they are popped off it) to solve the topological sorting
problem?
5. Apply the source-removal algorithm to the digraphs of Prohlem 1.
6. a. Prove that a dag must have at least one source.
b. How would you find a source (or determine that such a vertex does not
exist) in a digraph represented by its adjacency matrix? What is the time
efficiency of this operation?
c. How would you find a source (or determine that such a vertex does not
exist) in a digraph represented by its adjacency lists? What is the time
efficiency of this operation?
7. Can you implement the source-removal algorithm for a digraph represented
by its adjacency lists so that its running time is in O(IVI +lEI)?
8. Implement the two topological sorting algorithms in the language of your
choice. Run an experiment to compare their running times.
9. A digraph is called strongly connected if for any pair of two distinct vertices u
and v there exists a directed path from u to v and a directed path from v to u. In
general, a digraph's vertices can be partitioned into disjoint maximal subsets
of vertices that are mutually accessible via directed paths of the digraph; these
subsets are called strongly connected components. There are two DFS-based