DFS-Based Approach — Topological Sorting | OneNoughtOne

0/97

Data Structures & AlgorithmsTopological Sorting

Topological Sorting

LevelIntermediate

Duration60 mins

TopicTopological Sorting

4 / 5

DFS-Based Approach

Depth-First Search Meets Topological Ordering

The DFS-based approach to topological sorting is arguably even more elegant than Kahn's algorithm, though its correctness is less immediately obvious. It emerges from a profound observation about the relationship between DFS traversal order and dependency structure. The Key Insight: When performing DFS, we 'finish' a vertex (return from its recursive call) only after we've completely explored all vertices reachable from it. In a DAG, this means we finish a vertex only after finishing all its descendants—all vertices that depend on it. If we record vertices in the order they're finished (post-order), and then reverse this list, we get a topological ordering. Why? Because a vertex that others depend on will finish after those dependents, so reversing puts it before them—exactly what we need.

What You Will Learn

By the end of this page, you will understand the DFS-based topological sort algorithm, its connection to post-order traversal, how it detects cycles using edge classification, its implementation in both recursive and iterative forms, and when to prefer it over Kahn's algorithm.

Algorithm Overview

Let's state the DFS-based topological sort algorithm precisely: DFS Topological Sort Algorithm: Initialize: Mark all vertices as unvisited. Create an empty result list. DFS Traversal: For each unvisited vertex v: Mark v as 'currently visiting' (in progress) Recursively visit all unvisited neighbors of v After all neighbors are fully explored, mark v as 'visited' (done) Append v to the result list (post-order) Cycle Detection: If during step 2 we encounter a vertex that's 'currently visiting' (not 'visited', but 'in progress'), we've found a cycle—the graph is not a DAG. Reverse: The result list, built by appending at post-order, is in reverse topological order. Reverse it (or build it by prepending). The Three States: Unlike simple DFS that uses a binary visited flag, we need three states: WHITE (Unvisited): Not yet reached GRAY (Visiting): Currently in the DFS stack, being explored BLACK (Visited): Fully explored, all descendants processed

Graph:
    A ──► B ──► D
    │     │
    ▼     ▼
    C ──► E
 
DFS from A (assuming alphabetical order of neighbors):
 
Step 1: Visit A (A becomes GRAY)
  Step 2: Visit B (B becomes GRAY)
    Step 3: Visit D (D becomes GRAY)
      D has no unvisited neighbors
      D becomes BLACK, add D to result
      result = [D]
    Step 4: Visit E (E becomes GRAY)
      E has no unvisited neighbors
      E becomes BLACK, add E to result
      result = [D, E]
    B is done with neighbors
    B becomes BLACK, add B to result
    result = [D, E, B]
  Step 5: Visit C (C becomes GRAY)
    C's neighbor E is already BLACK (skip)
    C becomes BLACK, add C to result
    result = [D, E, B, C]
  A is done with neighbors
  A becomes BLACK, add A to result
  result = [D, E, B, C, A]
 
REVERSE the result:
Topological order = [A, C, B, E, D]
 
Verify: Every edge goes from left to right in this ordering ✓

Why Post-Order Reversal Works

This is the crucial insight that makes the algorithm work. Let's prove it carefully. Theorem: In a DAG, if we record vertices in DFS post-order and reverse the list, the result is a valid topological ordering. Proof: Consider any edge (u \to v) in the graph. We need to show that u appears before v in the reversed post-order list, which means u is recorded after v in the original post-order. There are two cases when we visit u: Case 1: v is unvisited when we visit u Since (u \to v) is an edge, we will visit v during the DFS from u (either directly or through some path). v will return from its recursive call before u returns from its call (nested structure of recursion). Therefore, v is added to the post-order list before u. When reversed, u comes before v. ✓ Case 2: v is already visited (BLACK) when we visit u v finished its DFS before we even started exploring u. So v is already in the post-order list when u is eventually added. Therefore, v comes before u in post-order, meaning u comes before v when reversed. ✓ Case 3: v is currently being visited (GRAY)? This would mean v is an ancestor of u in the DFS tree (u is reached while exploring v). But if (u \to v) exists and v is an ancestor of u, we have a path v \to ... \to u and an edge u \to v, forming a cycle! This contradicts our assumption that the graph is a DAG. Since case 3 is impossible in a DAG, the proof is complete.

The Cycle Detection Insight

Notice that Case 3 in the proof is exactly how we detect cycles! If we ever encounter a GRAY vertex while exploring, we've found a back edge—an edge from a descendant back to an ancestor—which creates a cycle. This is why the three-color marking is essential for cycle detection.

Recursive Implementation

The recursive implementation is clean and directly mirrors the algorithm description:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from enum import Enum
 
class State(Enum):
    WHITE = 0  # Unvisited
    GRAY = 1   # Currently visiting (in DFS stack)
    BLACK = 2  # Fully visited
 
def dfs_topological_sort(graph):
    """
    Topological sort using DFS post-order reversal.
    
    Args:
        graph: Dictionary mapping each vertex to its neighbors
        
    Returns:
        List of vertices in topological order, or None if cycle exists
    """
    state = {v: State.WHITE for v in graph}
    post_order = []
    has_cycle = False
    
    def dfs(vertex):
        nonlocal has_cycle
        
        if has_cycle:
            return  # Early exit if cycle already found
            
        state[vertex] = State.GRAY  # Mark as currently visiting
        
        for neighbor in graph[vertex]:
            if state[neighbor] == State.GRAY:
                # Found back edge - cycle detected!
                has_cycle = True
                return
            elif state[neighbor] == State.WHITE:
                dfs(neighbor)
                if has_cycle:
                    return
        
        # All neighbors explored - add to post-order
        state[vertex] = State.BLACK
        post_order.append(vertex)
    
    # Start DFS from each unvisited vertex
    for vertex in graph:
        if state[vertex] == State.WHITE:
            dfs(vertex)
            if has_cycle:
                return None
    
    # Reverse post-order to get topological order
    post_order.reverse()
    return post_order
 
 
# Example usage
dag = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E'],
    'D': [],
    'E': []
}
result = dfs_topological_sort(dag)
print(f"Topological order: {result}")  # e.g., ['A', 'C', 'B', 'E', 'D']
 
# Graph with cycle
cyclic = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']
}
result = dfs_topological_sort(cyclic)
print(f"Cyclic result: {result}")  # None

Alternative: Prepend Instead of Reverse

Instead of appending to post_order and reversing at the end, you can prepend each finished vertex (insert at front) or use a stack. This avoids the final reversal but may have slightly different performance characteristics depending on the data structure used.

TypeScript Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
enum VisitState {
    WHITE = 'unvisited',
    GRAY = 'visiting',
    BLACK = 'visited'
}
 
type Graph<T> = Map<T, T[]>;
 
interface TopSortResult<T> {
    order: T[] | null;
    hasCycle: boolean;
    cycleEdge: [T, T] | null;  // The back edge that created the cycle
}
 
function dfsTopologicalSort<T>(graph: Graph<T>): TopSortResult<T> {
    const state = new Map<T, VisitState>();
    const postOrder: T[] = [];
    let cycleEdge: [T, T] | null = null;
    
    // Initialize all vertices as unvisited
    for (const vertex of graph.keys()) {
        state.set(vertex, VisitState.WHITE);
    }
    
    function dfs(vertex: T): boolean {
        state.set(vertex, VisitState.GRAY);
        
        const neighbors = graph.get(vertex) ?? [];
        for (const neighbor of neighbors) {
            const neighborState = state.get(neighbor);
            
            if (neighborState === VisitState.GRAY) {
                // Back edge found - cycle!
                cycleEdge = [vertex, neighbor];
                return false;
            }
            
            if (neighborState === VisitState.WHITE) {
                if (!dfs(neighbor)) {
                    return false;  // Cycle found in subtree
                }
            }
            // If BLACK, already fully processed - skip
        }
        
        state.set(vertex, VisitState.BLACK);
        postOrder.push(vertex);
        return true;
    }
    
    // Visit all components
    for (const vertex of graph.keys()) {
        if (state.get(vertex) === VisitState.WHITE) {
            if (!dfs(vertex)) {
                return {
                    order: null,
                    hasCycle: true,
                    cycleEdge
                };
            }
        }
    }
    
    // Reverse to get topological order
    return {
        order: postOrder.reverse(),
        hasCycle: false,
        cycleEdge: null
    };
}
 
// Usage
const graph: Graph<string> = new Map([
    ['compile', ['link']],
    ['preprocess', ['compile']],
    ['link', ['deploy']],
    ['test', ['deploy']],
    ['deploy', []]
]);
 
const result = dfsTopologicalSort(graph);
if (result.order) {
    console.log('Build order:', result.order.join(' → '));
    // preprocess → compile → test → link → deploy
}

Iterative Implementation (Without Recursion)

For very deep graphs or environments with limited stack space, an iterative implementation using an explicit stack is preferable. The iterative version is more complex because we need to track when a vertex's exploration is complete: Challenge: In recursion, the 'post-order' action (adding to result) happens automatically when the function returns. With an explicit stack, we need to simulate this return. Solution: Push vertices twice or use a marker. When we pop a vertex, check if it's the 'first' visit (explore neighbors) or 'second' visit (add to result).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def iterative_dfs_topological_sort(graph):
    """
    Topological sort using iterative DFS with explicit stack.
    
    Uses (vertex, is_processed) tuples on the stack to track state.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    stack = []
    post_order = []
    
    for start in graph:
        if state[start] != WHITE:
            continue
            
        # Push start vertex with 'not yet processed' flag
        stack.append((start, False))
        
        while stack:
            vertex, is_processed = stack.pop()
            
            if is_processed:
                # Second visit: done exploring, add to post-order
                post_order.append(vertex)
                state[vertex] = BLACK
                continue
            
            if state[vertex] == GRAY:
                # Already in progress from another path - skip
                continue
                
            if state[vertex] == BLACK:
                # Already fully explored - skip
                continue
            
            # First visit: start exploring
            state[vertex] = GRAY
            
            # Push with 'is_processed=True' for post-order callback
            stack.append((vertex, True))
            
            # Push all WHITE neighbors
            for neighbor in graph[vertex]:
                if state[neighbor] == GRAY:
                    # Back edge - cycle detected!
                    return None
                if state[neighbor] == WHITE:
                    stack.append((neighbor, False))
    
    # Reverse for topological order
    post_order.reverse()
    return post_order
 
 
# Alternative: Using sentinel None values
def iterative_topo_sort_v2(graph):
    """Alternative using None as 'finished processing' marker."""
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    stack = []
    result = []
    
    for start in graph:
        if state[start] != WHITE:
            continue
        
        stack.append(start)
        
        while stack:
            v = stack.pop()
            
            if v is None:
                # Sentinel: next vertex is done
                done_vertex = stack.pop()
                result.append(done_vertex)
                state[done_vertex] = BLACK
                continue
            
            if state[v] == BLACK:
                continue
            if state[v] == GRAY:
                continue  # Will be handled by its sentinel
            
            state[v] = GRAY
            stack.append(v)      # Will be popped after sentinel
            stack.append(None)   # Sentinel marker
            
            for neighbor in graph[v]:
                if state[neighbor] == GRAY:
                    return None  # Cycle
                if state[neighbor] == WHITE:
                    stack.append(neighbor)
    
    result.reverse()
    return result

Iterative Complexity

The iterative version is harder to read and debug. Use it only when recursion depth is a genuine concern (very deep DAGs with thousands of levels). For most practical purposes, the recursive version is clearer.

Edge Classification in DFS

DFS naturally classifies edges based on the state of their endpoints. Understanding this classification deepens our understanding of cycle detection. Edge Types in Directed Graph DFS: When we're at vertex u and consider edge (u \to v):

DFS Edge Classification
Edge Type	State of v	Meaning	Cycle?
Tree Edge	WHITE	v is discovered via this edge; becomes child of u in DFS tree	No
Back Edge	GRAY	v is an ancestor of u in DFS tree; edge goes 'back up'	YES
Forward Edge	BLACK (descendant)	v is a descendant of u already fully explored	No
Cross Edge	BLACK (not descendant)	v is in a different subtree, already explored	No

Key Insight: A directed graph has a cycle if and only if DFS finds a back edge. Why only back edges indicate cycles? Tree edges are how we build the DFS tree—no cycle. Forward edges point to descendants already processed—the path tree edge \to forward edge doesn't form a cycle because forward edges go 'down' in the tree. Cross edges go between unrelated subtrees—no path back to current vertex. Back edges point to an ancestor—combined with tree edges down to current vertex, they form a cycle!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import defaultdict
 
def classify_edges_dfs(graph):
    """
    Perform DFS and classify all edges.
    
    Returns dict mapping (u, v) -> edge_type
    Also computes discovery and finish times for each vertex.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    discovery = {}  # When vertex was first visited
    finish = {}     # When vertex exploration completed
    edge_types = {}
    time = [0]  # Use list to allow modification in nested function
    
    def dfs(u, parent=None):
        state[u] = GRAY
        time[0] += 1
        discovery[u] = time[0]
        
        for v in graph[u]:
            if state[v] == WHITE:
                edge_types[(u, v)] = 'tree'
                dfs(v, u)
            elif state[v] == GRAY:
                edge_types[(u, v)] = 'back'  # CYCLE INDICATOR
            else:  # BLACK
                # Forward or cross - check discovery times
                if discovery[u] < discovery[v]:
                    edge_types[(u, v)] = 'forward'
                else:
                    edge_types[(u, v)] = 'cross'
        
        state[u] = BLACK
        time[0] += 1
        finish[u] = time[0]
    
    for v in graph:
        if state[v] == WHITE:
            dfs(v)
    
    return edge_types, discovery, finish
 
# Example
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
edges, disc, fin = classify_edges_dfs(graph)
print("Edge classifications:")
for (u, v), etype in edges.items():
    print(f"  {u} → {v}: {etype}")

Time and Space Complexity

Like Kahn's algorithm, DFS-based topological sort achieves optimal complexity. Time Complexity: O(V + E) The analysis is straightforward: Each vertex is visited exactly once (WHITE \to GRAY \to BLACK) Each edge is examined exactly once (when exploring from its source) The reversal at the end is O(V) Total: O(V + E) Space Complexity: O(V) State array/map: O(V) Post-order list: O(V) Recursion stack: O(V) in the worst case (a long chain graph) No per-edge storage Total: O(V)

Recursion Depth Warning

The recursive implementation can hit stack overflow on very deep graphs. If the longest path has more than ~1000-10000 vertices (depends on language/runtime), use the iterative version. In Python, you can also increase the recursion limit with sys.setrecursionlimit(), but the iterative approach is safer.

Space Usage Comparison
Implementation	Main Storage	Auxiliary	Stack Depth
Recursive	states O(V) + result O(V)	None	O(V) call stack
Iterative	states O(V) + result O(V)	explicit stack O(V)	O(1) call stack

Data Structures & AlgorithmsTopological Sorting

Topological Sorting

LevelIntermediate

Duration60 mins

TopicTopological Sorting

4 / 5

DFS-Based Approach

Depth-First Search Meets Topological Ordering

The DFS-based approach to topological sorting is arguably even more elegant than Kahn's algorithm, though its correctness is less immediately obvious. It emerges from a profound observation about the relationship between DFS traversal order and dependency structure. The Key Insight: When performing DFS, we 'finish' a vertex (return from its recursive call) only after we've completely explored all vertices reachable from it. In a DAG, this means we finish a vertex only after finishing all its descendants—all vertices that depend on it. If we record vertices in the order they're finished (post-order), and then reverse this list, we get a topological ordering. Why? Because a vertex that others depend on will finish after those dependents, so reversing puts it before them—exactly what we need.

What You Will Learn

By the end of this page, you will understand the DFS-based topological sort algorithm, its connection to post-order traversal, how it detects cycles using edge classification, its implementation in both recursive and iterative forms, and when to prefer it over Kahn's algorithm.

Algorithm Overview

Let's state the DFS-based topological sort algorithm precisely: DFS Topological Sort Algorithm: Initialize: Mark all vertices as unvisited. Create an empty result list. DFS Traversal: For each unvisited vertex v: Mark v as 'currently visiting' (in progress) Recursively visit all unvisited neighbors of v After all neighbors are fully explored, mark v as 'visited' (done) Append v to the result list (post-order) Cycle Detection: If during step 2 we encounter a vertex that's 'currently visiting' (not 'visited', but 'in progress'), we've found a cycle—the graph is not a DAG. Reverse: The result list, built by appending at post-order, is in reverse topological order. Reverse it (or build it by prepending). The Three States: Unlike simple DFS that uses a binary visited flag, we need three states: WHITE (Unvisited): Not yet reached GRAY (Visiting): Currently in the DFS stack, being explored BLACK (Visited): Fully explored, all descendants processed

Graph:
    A ──► B ──► D
    │     │
    ▼     ▼
    C ──► E
 
DFS from A (assuming alphabetical order of neighbors):
 
Step 1: Visit A (A becomes GRAY)
  Step 2: Visit B (B becomes GRAY)
    Step 3: Visit D (D becomes GRAY)
      D has no unvisited neighbors
      D becomes BLACK, add D to result
      result = [D]
    Step 4: Visit E (E becomes GRAY)
      E has no unvisited neighbors
      E becomes BLACK, add E to result
      result = [D, E]
    B is done with neighbors
    B becomes BLACK, add B to result
    result = [D, E, B]
  Step 5: Visit C (C becomes GRAY)
    C's neighbor E is already BLACK (skip)
    C becomes BLACK, add C to result
    result = [D, E, B, C]
  A is done with neighbors
  A becomes BLACK, add A to result
  result = [D, E, B, C, A]
 
REVERSE the result:
Topological order = [A, C, B, E, D]
 
Verify: Every edge goes from left to right in this ordering ✓

Why Post-Order Reversal Works

This is the crucial insight that makes the algorithm work. Let's prove it carefully. Theorem: In a DAG, if we record vertices in DFS post-order and reverse the list, the result is a valid topological ordering. Proof: Consider any edge (u \to v) in the graph. We need to show that u appears before v in the reversed post-order list, which means u is recorded after v in the original post-order. There are two cases when we visit u: Case 1: v is unvisited when we visit u Since (u \to v) is an edge, we will visit v during the DFS from u (either directly or through some path). v will return from its recursive call before u returns from its call (nested structure of recursion). Therefore, v is added to the post-order list before u. When reversed, u comes before v. ✓ Case 2: v is already visited (BLACK) when we visit u v finished its DFS before we even started exploring u. So v is already in the post-order list when u is eventually added. Therefore, v comes before u in post-order, meaning u comes before v when reversed. ✓ Case 3: v is currently being visited (GRAY)? This would mean v is an ancestor of u in the DFS tree (u is reached while exploring v). But if (u \to v) exists and v is an ancestor of u, we have a path v \to ... \to u and an edge u \to v, forming a cycle! This contradicts our assumption that the graph is a DAG. Since case 3 is impossible in a DAG, the proof is complete.

The Cycle Detection Insight

Notice that Case 3 in the proof is exactly how we detect cycles! If we ever encounter a GRAY vertex while exploring, we've found a back edge—an edge from a descendant back to an ancestor—which creates a cycle. This is why the three-color marking is essential for cycle detection.

Recursive Implementation

The recursive implementation is clean and directly mirrors the algorithm description:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from enum import Enum
 
class State(Enum):
    WHITE = 0  # Unvisited
    GRAY = 1   # Currently visiting (in DFS stack)
    BLACK = 2  # Fully visited
 
def dfs_topological_sort(graph):
    """
    Topological sort using DFS post-order reversal.
    
    Args:
        graph: Dictionary mapping each vertex to its neighbors
        
    Returns:
        List of vertices in topological order, or None if cycle exists
    """
    state = {v: State.WHITE for v in graph}
    post_order = []
    has_cycle = False
    
    def dfs(vertex):
        nonlocal has_cycle
        
        if has_cycle:
            return  # Early exit if cycle already found
            
        state[vertex] = State.GRAY  # Mark as currently visiting
        
        for neighbor in graph[vertex]:
            if state[neighbor] == State.GRAY:
                # Found back edge - cycle detected!
                has_cycle = True
                return
            elif state[neighbor] == State.WHITE:
                dfs(neighbor)
                if has_cycle:
                    return
        
        # All neighbors explored - add to post-order
        state[vertex] = State.BLACK
        post_order.append(vertex)
    
    # Start DFS from each unvisited vertex
    for vertex in graph:
        if state[vertex] == State.WHITE:
            dfs(vertex)
            if has_cycle:
                return None
    
    # Reverse post-order to get topological order
    post_order.reverse()
    return post_order
 
 
# Example usage
dag = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E'],
    'D': [],
    'E': []
}
result = dfs_topological_sort(dag)
print(f"Topological order: {result}")  # e.g., ['A', 'C', 'B', 'E', 'D']
 
# Graph with cycle
cyclic = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']
}
result = dfs_topological_sort(cyclic)
print(f"Cyclic result: {result}")  # None

Alternative: Prepend Instead of Reverse

Instead of appending to post_order and reversing at the end, you can prepend each finished vertex (insert at front) or use a stack. This avoids the final reversal but may have slightly different performance characteristics depending on the data structure used.

TypeScript Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
enum VisitState {
    WHITE = 'unvisited',
    GRAY = 'visiting',
    BLACK = 'visited'
}
 
type Graph<T> = Map<T, T[]>;
 
interface TopSortResult<T> {
    order: T[] | null;
    hasCycle: boolean;
    cycleEdge: [T, T] | null;  // The back edge that created the cycle
}
 
function dfsTopologicalSort<T>(graph: Graph<T>): TopSortResult<T> {
    const state = new Map<T, VisitState>();
    const postOrder: T[] = [];
    let cycleEdge: [T, T] | null = null;
    
    // Initialize all vertices as unvisited
    for (const vertex of graph.keys()) {
        state.set(vertex, VisitState.WHITE);
    }
    
    function dfs(vertex: T): boolean {
        state.set(vertex, VisitState.GRAY);
        
        const neighbors = graph.get(vertex) ?? [];
        for (const neighbor of neighbors) {
            const neighborState = state.get(neighbor);
            
            if (neighborState === VisitState.GRAY) {
                // Back edge found - cycle!
                cycleEdge = [vertex, neighbor];
                return false;
            }
            
            if (neighborState === VisitState.WHITE) {
                if (!dfs(neighbor)) {
                    return false;  // Cycle found in subtree
                }
            }
            // If BLACK, already fully processed - skip
        }
        
        state.set(vertex, VisitState.BLACK);
        postOrder.push(vertex);
        return true;
    }
    
    // Visit all components
    for (const vertex of graph.keys()) {
        if (state.get(vertex) === VisitState.WHITE) {
            if (!dfs(vertex)) {
                return {
                    order: null,
                    hasCycle: true,
                    cycleEdge
                };
            }
        }
    }
    
    // Reverse to get topological order
    return {
        order: postOrder.reverse(),
        hasCycle: false,
        cycleEdge: null
    };
}
 
// Usage
const graph: Graph<string> = new Map([
    ['compile', ['link']],
    ['preprocess', ['compile']],
    ['link', ['deploy']],
    ['test', ['deploy']],
    ['deploy', []]
]);
 
const result = dfsTopologicalSort(graph);
if (result.order) {
    console.log('Build order:', result.order.join(' → '));
    // preprocess → compile → test → link → deploy
}

Iterative Implementation (Without Recursion)

For very deep graphs or environments with limited stack space, an iterative implementation using an explicit stack is preferable. The iterative version is more complex because we need to track when a vertex's exploration is complete: Challenge: In recursion, the 'post-order' action (adding to result) happens automatically when the function returns. With an explicit stack, we need to simulate this return. Solution: Push vertices twice or use a marker. When we pop a vertex, check if it's the 'first' visit (explore neighbors) or 'second' visit (add to result).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def iterative_dfs_topological_sort(graph):
    """
    Topological sort using iterative DFS with explicit stack.
    
    Uses (vertex, is_processed) tuples on the stack to track state.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    stack = []
    post_order = []
    
    for start in graph:
        if state[start] != WHITE:
            continue
            
        # Push start vertex with 'not yet processed' flag
        stack.append((start, False))
        
        while stack:
            vertex, is_processed = stack.pop()
            
            if is_processed:
                # Second visit: done exploring, add to post-order
                post_order.append(vertex)
                state[vertex] = BLACK
                continue
            
            if state[vertex] == GRAY:
                # Already in progress from another path - skip
                continue
                
            if state[vertex] == BLACK:
                # Already fully explored - skip
                continue
            
            # First visit: start exploring
            state[vertex] = GRAY
            
            # Push with 'is_processed=True' for post-order callback
            stack.append((vertex, True))
            
            # Push all WHITE neighbors
            for neighbor in graph[vertex]:
                if state[neighbor] == GRAY:
                    # Back edge - cycle detected!
                    return None
                if state[neighbor] == WHITE:
                    stack.append((neighbor, False))
    
    # Reverse for topological order
    post_order.reverse()
    return post_order
 
 
# Alternative: Using sentinel None values
def iterative_topo_sort_v2(graph):
    """Alternative using None as 'finished processing' marker."""
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    stack = []
    result = []
    
    for start in graph:
        if state[start] != WHITE:
            continue
        
        stack.append(start)
        
        while stack:
            v = stack.pop()
            
            if v is None:
                # Sentinel: next vertex is done
                done_vertex = stack.pop()
                result.append(done_vertex)
                state[done_vertex] = BLACK
                continue
            
            if state[v] == BLACK:
                continue
            if state[v] == GRAY:
                continue  # Will be handled by its sentinel
            
            state[v] = GRAY
            stack.append(v)      # Will be popped after sentinel
            stack.append(None)   # Sentinel marker
            
            for neighbor in graph[v]:
                if state[neighbor] == GRAY:
                    return None  # Cycle
                if state[neighbor] == WHITE:
                    stack.append(neighbor)
    
    result.reverse()
    return result

Iterative Complexity

The iterative version is harder to read and debug. Use it only when recursion depth is a genuine concern (very deep DAGs with thousands of levels). For most practical purposes, the recursive version is clearer.

Edge Classification in DFS

DFS naturally classifies edges based on the state of their endpoints. Understanding this classification deepens our understanding of cycle detection. Edge Types in Directed Graph DFS: When we're at vertex u and consider edge (u \to v):

DFS Edge Classification
Edge Type	State of v	Meaning	Cycle?
Tree Edge	WHITE	v is discovered via this edge; becomes child of u in DFS tree	No
Back Edge	GRAY	v is an ancestor of u in DFS tree; edge goes 'back up'	YES
Forward Edge	BLACK (descendant)	v is a descendant of u already fully explored	No
Cross Edge	BLACK (not descendant)	v is in a different subtree, already explored	No

Key Insight: A directed graph has a cycle if and only if DFS finds a back edge. Why only back edges indicate cycles? Tree edges are how we build the DFS tree—no cycle. Forward edges point to descendants already processed—the path tree edge \to forward edge doesn't form a cycle because forward edges go 'down' in the tree. Cross edges go between unrelated subtrees—no path back to current vertex. Back edges point to an ancestor—combined with tree edges down to current vertex, they form a cycle!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import defaultdict
 
def classify_edges_dfs(graph):
    """
    Perform DFS and classify all edges.
    
    Returns dict mapping (u, v) -> edge_type
    Also computes discovery and finish times for each vertex.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    state = {v: WHITE for v in graph}
    discovery = {}  # When vertex was first visited
    finish = {}     # When vertex exploration completed
    edge_types = {}
    time = [0]  # Use list to allow modification in nested function
    
    def dfs(u, parent=None):
        state[u] = GRAY
        time[0] += 1
        discovery[u] = time[0]
        
        for v in graph[u]:
            if state[v] == WHITE:
                edge_types[(u, v)] = 'tree'
                dfs(v, u)
            elif state[v] == GRAY:
                edge_types[(u, v)] = 'back'  # CYCLE INDICATOR
            else:  # BLACK
                # Forward or cross - check discovery times
                if discovery[u] < discovery[v]:
                    edge_types[(u, v)] = 'forward'
                else:
                    edge_types[(u, v)] = 'cross'
        
        state[u] = BLACK
        time[0] += 1
        finish[u] = time[0]
    
    for v in graph:
        if state[v] == WHITE:
            dfs(v)
    
    return edge_types, discovery, finish
 
# Example
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
edges, disc, fin = classify_edges_dfs(graph)
print("Edge classifications:")
for (u, v), etype in edges.items():
    print(f"  {u} → {v}: {etype}")

Time and Space Complexity

Like Kahn's algorithm, DFS-based topological sort achieves optimal complexity. Time Complexity: O(V + E) The analysis is straightforward: Each vertex is visited exactly once (WHITE \to GRAY \to BLACK) Each edge is examined exactly once (when exploring from its source) The reversal at the end is O(V) Total: O(V + E) Space Complexity: O(V) State array/map: O(V) Post-order list: O(V) Recursion stack: O(V) in the worst case (a long chain graph) No per-edge storage Total: O(V)

Recursion Depth Warning

The recursive implementation can hit stack overflow on very deep graphs. If the longest path has more than ~1000-10000 vertices (depends on language/runtime), use the iterative version. In Python, you can also increase the recursion limit with sys.setrecursionlimit(), but the iterative approach is safer.

Space Usage Comparison
Implementation	Main Storage	Auxiliary	Stack Depth
Recursive	states O(V) + result O(V)	None	O(V) call stack
Iterative	states O(V) + result O(V)	explicit stack O(V)	O(1) call stack

DFS-Based Approach

Depth-First Search Meets Topological Ordering

Algorithm Overview

Why Post-Order Reversal Works

Recursive Implementation

TypeScript Implementation

Iterative Implementation (Without Recursion)

Edge Classification in DFS

Time and Space Complexity

There’s more to understand.

DFS-Based Approach

Depth-First Search Meets Topological Ordering

Algorithm Overview

Why Post-Order Reversal Works

Recursive Implementation

TypeScript Implementation

Iterative Implementation (Without Recursion)

Edge Classification in DFS

Time and Space Complexity

There’s more to understand.