Topological Sort Using DFS in DSA Typescript

Mental Model

We perform DFS on each node, first recursing on all its successors (nodes it points to, i.e., tasks that depend on it), then adding the node to the stack. Reversing the stack gives a topological order where for every edge u -> v, u comes before v.

Analogy: To assemble a toy car, you first recursively assemble all components that require the current part (like assembling the full car after wheels and body are ready, but in reverse: process dependents first). Finish order reversed ensures prerequisites first.

Graph:
A -> B -> C
↑
D

Topological order: D -> A -> B -> C (all arrows point forward)

Dry Run Walkthrough

Input: Graph edges: A->B, B->C, D->A (u->v means u prerequisite for v, do u before v)

Goal: Find an order to do tasks so for every edge u->v, u comes before v.

Step 1: Start DFS at node D

Visited: D
Stack: []

Why: Pick an unvisited node and begin DFS traversal.

Step 2: From D, visit A (successor)

Visited: D, A
Stack: []

Why: D -> A, so recurse on successor A first.

Step 3: From A, visit B (successor)

Visited: D, A, B
Stack: []

Why: A -> B, recurse on successor B.

Step 4: From B, visit C (successor)

Visited: D, A, B, C
Stack: []

Why: B -> C, recurse on successor C.

Step 5: C has no successors, add C to stack

Stack: [C]

Why: No outgoing edges, all successors processed (none), finish C.

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All successors of B (C) processed, finish B.

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All successors of A (B) processed, finish A.

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All successors of D (A) processed, finish D.

Result:

Topological order (reverse stack): D -> A -> B -> C

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<string, string[]> = new Map();

  addEdge(from: string, to: string): void {
    if (!this.adjacencyList.has(from)) this.adjacencyList.set(from, []);
    if (!this.adjacencyList.has(to)) this.adjacencyList.set(to, []);
    this.adjacencyList.get(from)!.push(to);
  }

  topologicalSort(): string[] {
    const visited = new Set<string>();
    const stack: string[] = [];

    const dfs = (node: string) => {
      visited.add(node); // mark node visited
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          dfs(neighbor); // recurse on successors first
        }
      }
      stack.push(node); // add after all successors
    };

    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        dfs(node); // start DFS if unvisited
      }
    }

    return stack.reverse(); // reverse for topo order (prereqs first)
  }
}

// Driver code
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('D', 'A');

const order = graph.topologicalSort();
console.log(order.join(' -> '));

visited.add(node); // mark node visited

Mark as visited before recursing to prevent revisits

for (const neighbor of this.adjacencyList.get(node) || []) { if (!visited.has(neighbor)) { dfs(neighbor); } }

Recurse on unvisited successors (dependents) first

stack.push(node); // add after all successors

Post-order: add node after processing all successors

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { dfs(node); } }

Handle disconnected components by starting DFS from each unvisited node

return stack.reverse(); // reverse for topo order (prereqs first)

Reverse post-order gives topological order

Output

D -> A -> B -> C

Complexity Analysis

Time: O(V + E) - visit each vertex and traverse each edge once

Space: O(V) for visited set, stack, and recursion depth

vs Alternative: Kahn's BFS uses in-degrees, same complexity but requires computing degrees; DFS simpler, no extra preprocessing

Edge Cases

Empty graph

Returns empty array

DSA Typescript

Loop over keys() which is empty

Single node, no edges

Returns [node]

DSA Typescript

dfs adds to visited, no neighbors, push to stack, reverse

Disconnected components

Multiple DFS calls handle all

DSA Typescript

Loop checks all keys if unvisited

Graph with cycle (not DAG)

Produces invalid order (doesn't detect cycle)

DSA Typescript

Add cycle detection with recursion stack or colors for production use

When to Use This Pattern

Need to order tasks/jobs/courses where prerequisites must precede dependents (DAG scheduling).

Common Mistakes

Mistake: Pushing node to stack before recursing on neighbors
Fix: Push after recursion (post-order) to ensure successors processed first

Mistake: Forgetting to handle multiple components
Fix: Loop over all nodes and DFS if unvisited

Mistake: Not reversing the stack
Fix: Reverse post-order traversal to get correct topo order

Summary

DFS-based topological sort: post-order traversal (recurse successors first), reverse finishing order.

Works on DAGs: linearizes partial order defined by edges.

Key insight: prereqs finish later in DFS (pushed later), appear earlier after reverse.