Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

6.7 Strong Components

A strongly connected component of a directed graph is a maximal set of vertices in which there is a path from any one vertex in the set to any other vertex in the set. Depth-first search can be used to determine strongly connected components of a directed graph efficiently.

Let G = (V, E) be a directed graph. We can partition V into equivalence classes Vi, 1≤i≤r, such that vertices v and w are equivalent if and only if there is a path from v to w and a path from w to v. Let Ei, 1≤i≤r, be the set of arcs with head and tail in Vi. The graphs Gi = (Vi, Ei) are called the strongly connected components

(or just strong components) of G. A directed graph with only one strong component is said to be strongly connected.

Example 6.17. Figure 6.32 illustrates a directed graph with the two strong components shown in Fig. 6.33.

Fig. 6.32. Directed graph.

Fig. 6.33. The strong components of the digraph of Fig. 6.32.

Note that every vertex of a directed graph G is in some strong component, but that certain arcs may not be in any component. Such arcs, called cross-component arcs, go from a vertex in one component to a vertex in another. We can represent the interconnections among the components by constructing a reduced graph for G. The vertices of the reduced graph are the strongly connected components of G. There is an arc from vertex C to a different vertex C' of the reduced graph if there is an arc in G from some vertex in the component C to some vertex in component C'. The

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (25 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

reduced graph is always a dag, because if there were a cycle, then all the components in the cycle would really be one strong component, meaning that we didn't compute strong components properly. Figure 6.34 shows the reduced graph for the digraph in Figure 6.32.

We shall now present an algorithm to find the strongly connected

Fig. 6.34. Reduced graph.

components of a given directed graph G.

1.Perform a depth-first search of G and number the vertices in order of completion of the recursive calls; i.e., assign a number to vertex v after line (4) of Fig. 6.24.

2.Construct a new directed graph Gr by reversing the direction of every arc in

G.

3.Perform a depth-first search on Gr starting the search from the highestnumbered vertex according to the numbering assigned at step (1). If the depthfirst search does not reach all vertices, start the next depth-first search from the highest-numbered remaining vertex.

4.Each tree in the resulting spanning forest is a strongly connected component of G.

Example 6.18. Let us apply this algorithm to the directed graph of Fig. 6.32, starting at a and progressing first to b. After step (1) we number the vertices as shown in Fig. 6.35. Reversing the direction of the arcs we obtain the directed graph Gr in Fig. 6.36.

Performing the depth-first search on Gr we obtain the depth-first spanning forest shown in Fig. 6.37. We begin with a as a root, because a has the highest number. From a we can only reach c and then b. The next tree has root d, since that is the highest numbered (and only) remaining vertex. Each tree in this forest forms a strongly connected component of the original directed graph.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (26 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

We have claimed that the vertices of a strongly connected component correspond precisely to the vertices of a tree in the spanning forest of the second depth-first search. To see why, observe that if v and w are vertices in the same strongly connected component, then there are paths in G from v to w and from w to v. Thus there are also paths from v to w and from w to v in Gr.

Suppose that in the depth-first search of Gr, we begin a search at some root x and reach either v or w. Since v and w are reachable from each other,

Fig. 6.35. After step 1.

Fig. 6.36. Gr.

Fig. 6.37.Depth-first spanning forest for Gr.

both v and w will end up in the spanning tree with root x.

Now suppose v and w are in the same spanning tree of the depth-first spanning forest of Gr. We must show that v and w are in the same strongly connected component. Let x be the root of the spanning tree containing v and w. Since v is a descendant of x, there exists a path in Gr from x to v. Thus there exists a path in G from v to x.

In the construction of the depth-first spanning forest of Gr, vertex v was still

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (27 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

unvisited when the depth-first search at x was initiated. Thus x has a higher number than v, so in the depth-first search of G, the recursive call at v terminated before the recursive call at x did. But in the depth-first search of G, the search at v could not have started before x, since the path in G from v to x would then imply that the search at x would start and end before the search at v ended.

We conclude that in the search of G, v is visited during the search of x and hence v is a descendant of x in the first depth-first spanning forest for G. Thus there exists a path from x to v in G. Therefore x and v are in the same strongly connected component. An identical argument shows that x and w are in the same strongly connected component and hence v and w are in the same strongly connected component, as shown by the path from v to x to w and the path from w to x to v.

Exercises

a.adjacency matrices,

b.linked adjacency lists, and

c.adjacency lists represented as in Fig. 6.5.

a.Use the algorithm Dijkstra to find the shortest paths from a to the other vertices.

b.Use the algorithm Floyd to find the shortest distances between

all pairs of points. Also construct the matrix P that lets us recover the shortest paths.

Represent the digraph of Fig. 6.38

a.by an adjacency matrix giving arc costs.

b.by a linked adjacency list with arc costs indicated.

6.1

Fig. 6.38. Directed graph with arc costs.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (28 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

Describe a mathematical model for the following scheduling problem. Given tasks T1, T2, . . . , Tn, which require times t1, t2, . . . , tn to

6.2complete, and a set of constraints, each of the form "Ti must be completed prior to the start of Tj," find the minimum time necessary to complete all tasks.

6.3

Implement the operations FIRST, NEXT, and VERTEX for digraphs represented by

6.4 In the digraph of Fig. 6.38

6.5

Write a complete program for Dijkstra's algorithm using a partially ordered tree as a priority queue and linked adjacency lists.

*6.6

Show that the program Dijkstra does not work correctly if arc costs can be negative.

**6.7

Show that the program Floyd still works if some of the arcs have negative cost but no cycle has negative cost.

Assuming the order of the vertices is a, b , . . . , f in Fig. 6.38, construct a

6.8depth-first spanning forest; indicate the tree, forward, back and cross arcs, and indicate the depth-first numbering of the vertices.

Suppose we are given a depth-first spanning forest, and we list in postorder each of the spanning trees (trees composed of spanning edges),

*6.9 from the leftmost to the rightmost. Show that this order is the same as the order in which the calls of dfs ended when the spanning forest was constructed.

A root of a dag is a vertex r such that every vertex of the dag can be

6.10reached by a directed path from r. Write a program to determine whether a dag is rooted.

Consider a dag with e arcs and with two distinguished vertices s and t.

*6.11

Construct an O (e) algorithm to find a maximal set of vertex disjoint paths from s to t. By maximal we mean no additional path may be added, but it does not mean that it is the largest size such set.

Construct an algorithm to convert an expression tree with operators + and

6.12* into a dag by sharing common subexpressions. What is the time complexity of your algorithm?

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (29 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

6.13

Construct an algorithm for evaluating an arithmetic expression represented as a dag.

6.14

Write a program to find the longest path in a dag. What is the time complexity of your program?

6.15 Find the strong components of Fig. 6.38.

*6.16

Prove that the reduced graph of the strong components of Section 6.7 must be a dag.

Draw the first spanning forest, the reverse graph, and the second spanning

6.17forest developed by the strong components algorithm applied to the digraph of Fig. 6.38.

6.18Implement the strong components algorithm discussed in Section 6.7.

Show that the strong components algorithm takes time O (e) on a directed

*6.19 ≤ graph of e arcs and n vertices, assuming n e.

Write a program that takes as input a digraph and two of its vertices. The *6.20 program is to print all simple paths from one vertex to the other. What is

the time complexity of your program?

A transitive reduction of a directed graph G = (V, E) is any graph G' with

*6.21

the same vertices but with as few arcs as possible, such that the transitive closure of G' is the same as the transitive closure of G. how that if G is a dag, then the transitive reduction of G is unique.

*6.22

Write a program to compute the transitive reduction of a digraph. What is the time complexity of your program?

G' = (V, E') is called a minimal equivalent digraph for a digraph G = (V,

*6.23

E) if E' is a smallest subset of E and the transitive closure of both G and G' are the same. Show that if G is acyclic, then there is only one minimal equivalent digraph, namely, the transitive reduction.

*6.24

Write a program to find a minimal equivalent digraph for a given digraph. What is the time complexity of your program?

*6.25

Write a program to find the longest simple path from a given vertex of a digraph. What is the time complexity of your program?

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (30 of 31) [1.7.2001 19:12:41]

Data Structures and Algorithms: CHAPTER 6: Directed Graphs

Bibliographic Notes

Berge [1958] and Harary [1969] are two good sources for additional material on graph theory. Some books treating graph algorithms are Deo [1975], Even [1980], and Tarjan [1983].

The single-source shortest paths algorithm in Section 6.3 is from Dijkstra [1959]. The all-pairs shortest paths algorithm is from Floyd [1962] and the transitive closure algorithm is from Warshall [1962]. Johnson [1977] discusses efficient algorithms for finding shortest paths in sparse graphs. Knuth [1968] contains additional material on topological sort.

The strong components algorithm of Section 6.7 is similar to one suggested by R. Kosaraju in 1978 (unpublished), and to one published by Sharir [1981]. Tarjan [1972] contains another strong components algorithm that needs only one depth-first search traversal.

Coffman [1976] contains many examples of how digraphs can be used to model scheduling problems as in Exercise 6.2. Aho, Garey, and Ullman [1972] show that the transitive reduction of a dag is unique, and that computing the transitive reduction of a digraph is computationally equivalent to computing the transitive closure (Exercises 6.21 and 6.22). Finding the minimal equivalent digraph (Exercises 6.23 and 6.24), on the other hand, appears to be computationally much harder; this problem is NP-complete [Sahni (1974)].

†This is another manifestation of the old Pascal problem of doing insertion and deletion at arbitrary positions of singly linked lists.

†One might expect that a more natural problem is to find the shortest path from the source to one particular destination vertex. However, that problem appears just as hard in general as the single-source shortest paths problem (except that by luck we may find the path to the destination before some of the other vertices and thereby terminate the algorithm a bit earlier than if we wanted paths to all the vertices).

‡ We might assume that an undirected graph would be used here, since the label on arcs v → w and w → v would be the same. However, in fact, travel times are different in different directions because of prevailing winds. Anyway, assuming that labels on v → w and w → v are identical doesn't seem to help solve the problem.

Table of Contents Go to Chapter 7

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1206.htm (31 of 31) [1.7.2001 19:12:41]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_1.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_1.gif [1.7.2001 19:12:46]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_6.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_6.gif [1.7.2001 19:12:50]

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_7.gif

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/images/f5_7.gif [1.7.2001 19:12:55]