Lesson 5 � Intermediate

Topological Sort & Cycle Detection

Topological sort sirf DAGs (Directed Acyclic Graphs) par kaam karta hai. Yeh ek linear ordering deta hai jismein agar u ✓ v edge hai toh u pehle aayega. Course prerequisites jaise problems solve karta hai.

DAG kya hota hai?

DAG = Directed Acyclic Graph. Directed graph hai jismein koi cycle nahi hai.

Real-world example: Course prerequisites. Agar Course C ke liye pehle Course A aur B lena zaroori hai, toh yeh ek DAG hai. A ✓ C aur B ✓ C edges hain. C pehle nahi le sakte � pehle A aur B complete karo.

Course Prerequisites:
 A ---> C
 B ---> C
 B ---> D
 C ---> E

Valid topological orders:
[A, B, C, D, E] ya [B, A, D, C, E] (kai valid orders ho sakte hain)

Kahn's Algorithm (BFS-based)

Kahn's algorithm BFS use karta hai. Approach:

1. Sab vertices ki in-degree nikalo (kitne edges aa rahe hain).
2. Jin vertices ki in-degree = 0 hain unhe queue mein daalo.
3. Queue se nikalo, output mein add karo, aur uske sab neighbors ki in-degree ek se kam karo.
4. Agar kisi neighbor ki in-degree 0 ho jaye toh queue mein daalo.
5. Jab tak queue khali na ho jaye repeat karo.

from collections import deque

def topo_sort_kahn(graph, indegree):
 queue = deque([n for n in indegree if indegree[n] == 0])
 order = []
 
 while queue:
 node = queue.popleft()
 order.append(node)
 for neighbor in graph[node]:
 indegree[neighbor] -= 1
 if indegree[neighbor] == 0:
 queue.append(neighbor)
 
 # Agar order mein sab nodes nahi hain toh cycle hai
 if len(order) != len(indegree):
 return None # Cycle detected!
 return order

DFS-based Topological Sort

DFS wala approach recursion karta hai, jab sab children visit ho jayein tab current node ko stack mein daalte hain. End mein stack reverse karo � yeh topological order hai.

def topo_sort_dfs(graph, n):
 visited = set()
 stack = []
 
 def dfs(node):
 visited.add(node)
 for neighbor in graph[node]:
 if neighbor not in visited:
 dfs(neighbor)
 stack.append(node)
 
 for i in range(n):
 if i not in visited:
 dfs(i)
 
 return stack[::-1] # Reverse karo

Cycle Detection using Topological Sort

Topological sort se cycle detect karna aasan hai:

• Kahn's approach: Agar topological order mein sab nodes nahi aayin (order length < V), toh cycle hai.
• DFS approach: Recursion stack mein wapas aana matlab cycle hai.

def has_cycle(graph, n):
 visited = [0] * n # 0=unvisited, 1=visiting, 2=visited
 
 def dfs(node):
 visited[node] = 1
 for neighbor in graph[node]:
 if visited[neighbor] == 1:
 return True # Cycle hai!
 if visited[neighbor] == 0:
 if dfs(neighbor):
 return True
 visited[node] = 2
 return False
 
 for i in range(n):
 if visited[i] == 0:
 if dfs(i):
 return True
 return False

Real-world Applications

• Course Schedule (LeetCode 207, 210): Courses ka order nikalo prerequisites ke according.
• Build Systems: File dependencies � pehle dependencies build karo.
• Task Scheduling: Parallel tasks jo dependencies hain unka order.
• Spreadsheet Formulas: Cell references ka calculation order.

Try it: code khud likho

Graph (directed):
0 ? 1, 0 ? 2, 1 ? 3, 2 ? 3, 3 ? 4

Common mistakes

• Cyclic graph par topological sort lagana � infinite loop mein phas jaoge ya partial order aayega.
• Undirected graph par topological sort lagana � yeh sirf directed graphs ke liye hai.
• DFS-based approach mein recursion stack check karna bhool jaana � cycle detect nahi hogi.
• Kahn's algorithm mein in-degree update karna bhool jaana � nodes skip ho jayengi.
• Multiple valid topological orders mein se ek hi sahi hai sochna � kai valid orders ho sakte hain.