Topological Sort

Directed acyclic graphs or DAG's are used for our topological sorts. A topological sort of a DAG G = ( V, E )  is a linear ordering of v Î V such that if ( u, v ) Î E then u appears before v in this ordering. If G is cyclic, no such ordering exists:

Topological sort can also be viewed as placing all the vertices along a horizontal line so that all directed edges go from left to right. DAG's are used in many applications to indicate precedence.

The following algorithm does a topological sort on a DAG:

Topological-Sort (G)

1. Call DFS ( G ) to compute f[v] " v Î V
2. As each vertex is finished put it into the front of a linked list
3. Return the linked lise of vertices

Since DFS ( G ) takes Q ( | V | + | E | ) and insertion into the linked list cost O ( 1 ) for each of | V | insertions, topological sort costs only  Q ( | V | + | E | ). We now prove this algorithm correct:

Lemma: A directed graph, G, is acyclic Û DFS ( G ) yields no back edges

Proof: Suppose ( u, v ) is a back edge, then v is an ancestor of u in the depth-first forest. There is a path from v to u in G and so ( u, v ) completes a cycle, a contradiction. Suppose G has a cycle, c. Let v be the first edge discovered in DFS ( G ) of c and let ( u, v ) be the preceding edge in c. At time d[v] $ a path of white vertices from v to u and so by the white path theorem u is a descendant of v and so ( u, v ) is a back edge.

Theorem: Topological-Sort ( G ) produces a topological sort of DAG, G.

Proof: Run DFS ( G ) to determine finishing times. We must show that for any u, v Î V, if ( u, v ) Î G then f ( v ) < f ( u ). Consider any ( u, v ) explored by DFS ( G ). When explored, v cannot be gray since v would be an ancestor of u making ( u, v ) a back edge. By the lemma the G is not a DAG. Thus v is white or black, if white it is a descendant of u and f[v] < f[u]. If black then also  f[v] < f[u].