Topological Sort

SOF105
Graphs

SOF105 Data Structure

Introduction

• There are many problems involving a set of tasks in which

some of the tasks must be done before others.
• For example, consider the problem of taking a course only
after taking its prerequisites.
• Is there any systematic way of linearly arranging the
courses in the order that they should be taken?

Yes! - Topological sort.

SOF105 Data Structure
What is a DAG?

• A directed acyclic graph (DAG) is a directed graph without cycles.

Example:

• DAGs arise in modeling many problems that involve prerequisite constraints (construction projects, course prerequisites,
document version control, compilers, etc.)
• Some properties of DAGs:
• Every DAG must have at least one vertex with in-degree zero and at least one vertex with out-degree zero
• A vertex with in-degree zero is called a source vertex, a vertex with out-degree zero is called a sink vertex.
• G is a DAG iff each vertex in G is in its own strongly connected component
• Every edge (v, w) in a DAG G has finishingTime[w] < finishingTime[v] in a DFS traversal of G

SOF105 Data Structure

Definition of Topological Sort

• Given a directed graph G = (V, E) a topological sort of G is an

ordering of V such that for any edge (u, v), u comes before v in
the ordering.
• Example1:

• Example2:

SOF105 Data Structure

Definition of Topological Sort

• Example3: The graph in (a) can be topologically sorted as in (b)

(a) (b)

SOF105 Data Structure

Topological Sort is not unique

• Topological sort is not unique.

• The following are all topological sort of the graph below:

s1 = {a, b, c, d, e, f, g, h, i}

s2 = {a, c, b, f, e, d, h, g, i}

s3 = {a, b, d, c, e, g, f, h, i}

s4 = {a, c, f, b, e, h, d, g, i}
etc.

SOF105 Data Structure

Topological Sort Algorithms: DFS based algorithm
Topological-Sort(G)
{
1. Call dfsAllVertices on G to compute f[v] for each vertex v
2. If G contains a back edge (v, w) (i.e., if f[w] > f[v]) , report error ;
3. else, as each vertex is finished prepend it to a list; // or push in stack
4. Return the list; // list is a valid topological sort
}
• Running time is O(V+E), which is the running time for DFS.

Topological order: A C D B E H F G

SOF105 Data Structure

Topological Sort Algorithms: Source Removal Algorithm

• The Source Removal Topological sort algorithm is:

• Pick a source u [vertex with in-degree zero], output it.
• Remove u and all edges out of u.
• Repeat until graph is empty.

SOF105 Data Structure

Topological Sort: Source Removal Example
• The number beside each vertex is the in-degree of the vertex at the start of the algorithm.
1 2 3 0 2
A B C D E

F G H I J
1 0 2 2 0

D G A B F H J E I C

SOF105 Data Structure

Implementation of Topological Sort

• The algorithm is implemented as a traversal method that visits the vertices in a topological sort
order.

• An array of length |V| is used to record the in-degrees of the vertices. Hence no need to remove
vertices or edges.

• A priority queue is used to keep track of vertices with in-degree zero that are not yet visited.

SOF105 Data Structure

Review Questions

1. List the order in which the nodes of the directed graph GB are visited by
topological order traversal that starts from vertex a. Use both DFS-based and
Source Removal algorithm

2. What kind of DAG has a unique topological sort?

SOF105 Data Structure

Topological Sort: DFS
C

G A B

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)

G A B

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)

G A B

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)
dfs(E)

G A B

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B dfs(H)

D E

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B

D E

H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)
dfs(E)

G A B

D E

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)

G A B

D E
5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)
dfs(D)

G A B

D E
5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)

G A B

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(A)

G A B

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C

G A 3 B

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(B)

G A 3 B

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(B)

G A 3 B

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)
dfs(G)

G A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
C
dfs(C)

G 1 A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
0 C

G 1 A 3 B 2

D E
4 5

6
H
7

SOF105 Data Structure

Topological Sort: DFS
0 C

G 1 A 3 B 2

D E
4 5

6
H
7 Topological order: C G B A D E F H

SOF105 Data Structure

 Q/A

SOF105 Data Structure