Topological Sorting Using DFS

Topological sorting is an important application of Depth-First Search (DFS) 

It is used for directed acyclic graphs (DAGs), where the directed edges represent precedence or dependency relationships. 

---

1. What is Topological Sorting?

Let

$$G=(V,E)$$

be a directed graph.

A topological ordering is a linear ordering of all vertices such that:

$$(u,v)\in E$$

implies that u appears before v in the ordering.

In simple words:

If there is a directed edge from u to v, then u must come before v.

For example:

A → B

requires:

A, B

and not:

B, A

---

2. Topological Sorting Is Possible Only for a DAG

A DAG is a:

Directed Acyclic Graph

That means:

• The graph is directed.
• The graph contains no directed cycle.

Consider:

A → B → C

This is a DAG, so a topological ordering exists.

For example:

A, B, C

---

A graph containing a cycle

Consider:

A → B → C
↑       |
└───────┘

There is a cycle:

A → B → C → A

For a topological ordering, we would need:

A before B
B before C
C before A

which is impossible.

Therefore:

A directed graph has a topological ordering iff it is acyclic.​

---

3. Intuitive Interpretation

Think of the vertices as tasks and the edges as dependencies.

For example:

Learn C
   ↓
Learn Data Structures
   ↓
Learn Algorithms

The edge:

C → Data Structures

means:

Learn C before Data Structures.

Similarly:

Data Structures → Algorithms

means:

Learn Data Structures before Algorithms.

A valid topological ordering is:

C → Data Structures → Algorithms

---

4.  Example: Getting Dressed

When Professor Bumstead gets dressed in the morning. The professor must don certain garments before others (e.g., socks before shoes). Other items may be put on in any order (e.g., socks and pants). A directed edge (u, v) in the dag of Figure 20.7(a) indicates that garment u must be donned before garment v. A topological sort of this dag therefore gives a possible order for getting dressed. Figure 20.7(b) shows the topologically sorted dag as an ordering of vertices along a horizontal line such that all directed edges go from left to right.

One possible topological ordering could be:The important point is that there may be more than one valid topological ordering.

For example, if there is no dependency between socks and shirt, their relative order can be changed.

---

5. Procedure TOPOLOGICAL SORT

The procedure is remarkably simple:

TOPOLOGICAL-SORT(G)

1. Call DFS(G) to compute finishing times v.f
   for every vertex v.

2. As each vertex is finished,
   insert it at the front of a linked list.

3. Return the linked list.

The important idea is:

Topological sorting using DFS orders the vertices in decreasing order of their DFS finishing times.

That is:

Topological order = decreasing finish time​

---

6. Detailed Example

Consider this DAG:

        A
       / \
      B   C
      |   |
      D   E
       \ /
        F

Let the adjacency lists be examined in the following order:

Adj[A] = B, C
Adj[B] = D
Adj[C] = E
Adj[D] = F
Adj[E] = F
Adj[F] = empty

Suppose DFS starts with A.

---

Step 1: Discover A

A.d = 1

DFS goes to B.

---

Step 2: Discover B

B.d = 2

DFS goes to D.

---

Step 3: Discover D

D.d = 3

DFS goes to F.

---

Step 4: Discover F

F.d = 4

F has no outgoing edges.

Therefore F finishes:

F.f = 5

Insert F at the front:

F

---

Step 5: Finish D

There are no more unexplored edges from D.

Therefore:

D.f = 6

Insert D at the front:

D → F

---

Step 6: Finish B

B has no more unexplored edges.

Therefore:

B.f = 7

Insert B at the front:

B → D → F

---

Step 7: Return to A and Explore C

DFS now explores C.

C.d = 8

C goes to E.

E.d = 9

E has an edge to F, but F is already BLACK.

E therefore finishes:

E.f = 10

Insert E at front:

E → B → D → F

Then C finishes:

C.f = 11

Insert C:

C → E → B → D → F

Finally A finishes:

A.f = 12

Insert A:

A → C → E → B → D → F

Therefore, the topological ordering is:

A, C, E, B, D, F​

---

7. Verify the Ordering

Let's check every edge.

Edge	Ordering	Valid?
A → B	A before B	✓
A → C	A before C	✓
B → D	B before D	✓
C → E	C before E	✓
D → F	D before F	✓
E → F	E before F	✓

Therefore:

A → C → E → B → D → F

is a valid topological ordering.

Notice that:

B and C

could potentially be exchanged, depending on the DFS order.

Thus, a DAG can have multiple valid topological orderings.

---

8. Why Does Decreasing Finish Time Work?

This is the central theoretical idea.

Consider a directed edge:

(u,v)

in a DAG.

We want:

u before v

in the topological ordering.

DFS gives us:

$$u.f>v.f$$

Therefore, when vertices are arranged in decreasing order of finishing time:

larger finish time
       ↓
      u
       ↓
      v
       ↓
smaller finish time

we get:

u before v

which satisfies the edge constraint.

Therefore:

Decreasing DFS finishing times gives a topological ordering.​

---

9. Complexity Analysis

The topological sort  procedure runs in:

Θ(V+E)​

Let's see why.

Step 1: DFS

DFS takes:

$$\Theta (V+E)$$

time when the graph is represented using adjacency lists.

Step 2: Insert vertices into linked list

There are V vertices.

Each vertex is inserted at the front of the linked list.

Insertion at the front takes:

Θ(1)

Therefore:

$$V\times \Theta (1)=\Theta (V)$$

Total

$$\Theta (V+E)+\Theta (V)$$

which simplifies to:

Θ(V+E)​

---

10. Summary

Definition

A topological ordering of a DAG is a linear ordering of all vertices such that:

$$(u,v)\in E\Rightarrow u\text{appears before}v$$

DFS method

1. Run DFS.
2. Record the finishing time of every vertex.
3. Whenever a vertex finishes, insert it at the front of a linked list.
4. Return the linked list.

Therefore:

Topological order = vertices in decreasing DFS finishing time​

Important condition

Topological sorting is possible only for a DAG​

A back edge indicates a cycle:

Back edge⇒No topological ordering​

Complexity

Θ(V+E)​

because:

DFS  (V+E)​​+ linked-list insertion Θ(V)​​ = Θ(V+E)​

Key intuition

DFS finishes a vertex only after all vertices reachable through its outgoing edges have been processed. Therefore, in a DAG, a vertex that must come before another vertex gets a larger finishing time. Reversing the finishing order gives a valid topological ordering.