IntermediateGraphs

Topological Sort

Order DAG vertices so edges go forward; detect cycles via DFS or Kahn's algorithm

Time: O(V+E)
Space: O(V+E)
Pattern Overview

Core Idea

Use indegrees (Kahn) or DFS finishing times to produce a linear order for DAGs.

When to Use

Use when dependencies exist and tasks must be ordered before execution.

General Recognition Cues
General indicators that this pattern might be applicable
  • DAG
  • Prerequisite graph
  • Cycle detection
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Kahn's Algorithm

Process zero-indegree queue

When to Use This Variant
  • Indegree array
Use Case
DAG order
Advantages
  • Detects cycles
  • Iterative
Implementation
from collections import deque
def topo_kahn(n, edges):
    adj=[[] for _ in range(n)]; indeg=[0]*n
    for u,v in edges: adj[u].append(v); indeg[v]+=1
    q=deque([i for i in range(n) if indeg[i]==0]); order=[]
    while q:
        u=q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v]-=1
            if indeg[v]==0: q.append(v)
    return order if len(order)==n else []
2

DFS-based

Postorder push to stack

When to Use This Variant
  • Visited colors
Use Case
DAG order
Advantages
  • Elegant
  • Cycle via gray visited
Implementation
def topo_dfs(n, edges):
    adj=[[] for _ in range(n)];
    for u,v in edges: adj[u].append(v)
    vis=[0]*n; order=[]; ok=True
    def dfs(u):
        nonlocal ok
        vis[u]=1
        for v in adj[u]:
            if vis[v]==0: dfs(v)
            elif vis[v]==1: ok=False
        vis[u]=2; order.append(u)
    for i in range(n):
        if vis[i]==0: dfs(i)
    return order[::-1] if ok else []
3

Cycle Detection

Detect back edges/remaining indegrees

When to Use This Variant
  • No order exists
Use Case
Validate schedule
Advantages
  • Clear failure mode
Implementation
def has_cycle_kahn(n, edges):
    return len(topo_kahn(n, edges)) == 0
Common Pitfalls
Watch out for these common mistakes
  • Not counting indegrees accurately
  • Forgetting to detect cycles
  • Pushing nodes twice
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(V+E)

Each edge/vertex processed once.

Space Complexity
O(V+E)

Graph + indegree arrays.

Ready to test your knowledge?

Test your pattern recognition with interactive questions