Topological sort — DFS-based, Kahn's algorithm (BFS-based)

3.5.7 · Coding › Graphs

Topological sort HAI kya?

Cycle kyun ise tod deti hai? Agar $a\to b\to c\to a$ hai, toh $a$ ko $b$ se pehle, $b$ ko $c$ se pehle, aur $c$ ko $a$ se pehle aana chahiye. Iska matlab $a$ ko $a$ se pehle aana padega — jo impossible hai. Isliye cycles ⇒ koi topological order nahi.

DO algorithms kyun hain?

Dono same problem solve karte hain lekin sochne ka tarika alag hai:

Dono $O(V+E)$ mein chalte hain.

Algorithm 1 — DFS-based

Yeh kaise kaam karta hai (first principles se derivation)

Claim: Agar hum DFS ke vertices finish karne ka order reverse karein, toh har edge aage point karegi.

Koi bhi edge $u\to v$ lo. Jab DFS pehli baar $u$ ko touch kare, $v$ ki state consider karo:

• $v$ unvisited: DFS, $v$ ko $u$ ke descendant ki tarah explore karega, isliye $v$ $u$ se pehle finish hoga. ✅ ($u$ baad mein finish hoga ⇒ reversed order mein $u$ pehle)
• $v$ already finished: toh $v$, $u$ ke start hone se pehle hi finish ho chuka tha. ✅
• $v$ in progress (gray, stack par): iska matlab $v⇝u$ ka path already hai, saath mein edge $u\to v$ bhi = ek cycle. DAG mein allowed nahi. ❌ blocked.

Har valid (DAG) case mein, $u$ $v$ ke baad finish hota hai, toh reversed finish list mein $u$, $v$ se pehle aata hai. Edge aage point karti hai. ∎

function topoDFS(G):
    visited = {}, finished = []
    for each vertex u in V:
        if u not visited: dfs(u)
    return reverse(finished)

function dfs(u):
    mark u visited (GRAY)
    for each edge u -> v:
        if v GRAY:  report CYCLE   # back edge
        if v not visited: dfs(v)
    mark u BLACK
    finished.append(u)             # append on FINISH

Algorithm 2 — Kahn's Algorithm (BFS-based)

Yeh kaise kaam karta hai (derivation)

Define karo $\text{indeg}(v)$ = $v$ mein point karne wali edges ki sankhya.

1. Ek DAG mein hamesha kam se kam ek vertex hoti hai jiska indegree 0 ho (warna incoming edges ko backward follow karte raho ⇒ repeat ⇒ cycle). Toh hum hamesha start kar sakte hain.
2. Ek 0-indegree vertex ko emit karke uski out-edges delete karne se baaki graph DAG hi rehta hai. Induction se poora graph khali ho jaata hai.
3. Har edge aage point karti hai: jab hum $u$ emit karte hain, $u$ ke saare prerequisites already emit ho chuke hain; edge $u\to v$, $\text{indeg}(v)$ ko decrement karti hai, toh $v$ strictly baad mein emit hota hai. ✅

function kahn(G):
    compute indeg[v] for all v
    Q = queue of all v with indeg[v] == 0
    order = []
    while Q not empty:
        u = Q.pop()
        order.append(u)
        for each edge u -> v:
            indeg[v] -= 1
            if indeg[v] == 0: Q.push(v)
    if len(order) < |V|: report CYCLE   # leftover nodes stuck in a cycle
    return order

Worked Example (same graph, dono methods)

Graph edges: 5→0, 5→2, 4→0, 4→1, 2→3, 3→1 Vertices: 0 1 2 3 4 5

Kahn's walk-through

Indegrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0

Order: 4 5 0 2 3 1 — Yeh step kyun? Humne hamesha indegree-0 node pull kiya, jo guarantee karta hai ki har prerequisite pehle hi bahar aa chuka tha. 6 emit = |V| ⇒ valid DAG.

DFS walk-through (5 se start, phir 4)

• dfs(5)→dfs(0) finish 0 →dfs(2)→dfs(3)→dfs(1) finish 1, finish 3, finish 2, finish 5
• dfs(4): 0,1 done → finish 4
• finished list = [0,1,3,2,5,4]
• Reverse = 4 5 2 3 1 0

Yeh step kyun? Hum har node ko tabhi append karte hain jab uske descendants finish ho jaayein, isliye reverse karne par roots pehle aa jaate hain. (Note: Kahn se alag valid order — dono correct hain!)

Common Mistakes

Active Recall

Connections

• Depth-First Search (DFS) — DFS-topo bas DFS + finish-time ordering hai.
• Breadth-First Search (BFS) — Kahn's, indegree se driven BFS hai.
• Directed Acyclic Graph (DAG) — kisi bhi topo order ke liye precondition.
• Cycle Detection in Directed Graphs — dono algorithms cycles ko byproduct ke taur par detect karte hain.
• Course Schedule Problem — topological sort ka classic application.
• Shortest Path in DAG) — $O(V+E)$ shortest paths ke liye topological order mein edges relax karo.
• Strongly Connected Components — Kosaraju bhi isi tarah DFS finish ordering use karta hai.

Concept Map