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.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To visit nodes in depth-first order and record finishing times

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, exploring all descendants before finishing a node.

2. Step 2: Use finishing times to order nodes

   Nodes are added to the result stack after all descendants are visited, ensuring dependencies come first.

3. Final Answer:

   To visit nodes in depth-first order and record finishing times -> Option A

4. Quick Check:

   DFS finishing times = Topological order [OK]

Hint: DFS finishing order gives topological sort order [OK]

Common Mistakes:

• Confusing DFS with BFS for topological sort
• Thinking topological sort finds shortest paths
• Assuming topological sort works on undirected graphs

2. Which of the following TypeScript code snippets correctly initializes the adjacency list for a graph with 3 nodes for topological sort?

easy

A. const graph: number[][] = new Array(3);

B. const graph: number[] = [[], [], []];

C. const graph: number[][] = [[], [], []];

D. const graph: number[][] = new Array(3).fill([]);

Solution

1. Step 1: Check adjacency list type

   Adjacency list is an array of arrays: number[][].

2. Step 2: Verify initialization correctness

   const graph: number[][] = [[], [], []]; creates three separate empty arrays, one per node. const graph: number[][] = new Array(3).fill([]); fills with same array reference, causing bugs.

3. Final Answer:

   const graph: number[][] = [[], [], []]; -> Option C

4. Quick Check:

   Separate arrays per node = correct adjacency list [OK]

Hint: Use separate arrays for each node, not shared references [OK]

Common Mistakes:

• Using number[] instead of number[][] for adjacency list
• Using fill([]) causing shared references
• Not initializing arrays before adding edges

3. Given the following graph edges: 0 -> 1, 0 -> 2, 1 -> 2, what is the topological sort order using DFS?

const graph = [ [1, 2], [2], [] ];

medium

A. [0, 1, 2]

B. [2, 1, 0]

C. [1, 0, 2]

D. [0, 2, 1]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then 1, then 2. Add nodes to stack after visiting descendants: push 2, then 1, then 0.

2. Step 2: Reverse stack to get topological order

   Stack is [2,1,0], reversed is [0,1,2].

3. Final Answer:

   [0, 1, 2] -> Option A

4. Quick Check:

   DFS post-order reversed = [0,1,2] [OK]

Hint: Reverse DFS finishing order for topological sort [OK]

Common Mistakes:

• Not reversing the DFS finishing stack
• Visiting nodes in wrong order
• Confusing adjacency list direction

4. Identify the bug in this TypeScript DFS topological sort snippet:

function dfs(node: number, graph: number[][], visited: boolean[], stack: number[]) {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) dfs(neighbor, graph, visited, stack);
  }
  stack.push(node);
}

const graph = [ [1], [2], [] ];
const visited = [false, false, false];
const stack = [];
dfs(0, graph, visited, stack);
console.log(stack);

medium

A. Neighbors should be iterated in reverse order

B. Visited array is not initialized correctly

C. DFS should mark visited after recursion

D. The stack should be reversed before printing

Solution

1. Step 1: Understand DFS stack usage

   Nodes are pushed after visiting descendants, so stack has reverse topological order.

2. Step 2: Check output correctness

   Printing stack directly shows reverse order; reversing stack gives correct topological order.

3. Final Answer:

   The stack should be reversed before printing -> Option D

4. Quick Check:

   Reverse stack for correct order [OK]

Hint: Always reverse stack after DFS for topological order [OK]

Common Mistakes:

• Printing stack without reversing
• Marking visited after recursion causing repeated visits
• Incorrect initialization of visited array

5. You have a directed graph representing tasks with dependencies:

const graph = [ [2], [2, 3], [4], [4], [] ];

Which topological order is valid for completing all tasks?

hard

A. [2, 1, 0, 3, 4]

B. [0, 1, 3, 2, 4]

C. [1, 0, 3, 4, 2]

D. [0, 2, 1, 3, 4]

Solution

1. Step 1: Analyze dependencies

   Edges: 0->2 (0 before 2), 1->2 & 1->3 (1 before 2,3), 2->4 & 3->4 (2,3 before 4).

2. Step 2: Find order respecting dependencies

   Only D [0, 1, 3, 2, 4] works: 0(pos0)<2(3); 1(1)<2(3),3(2); 2(3)<4(4), 3(2)<4(4). A: 2 first before 0,1. B: 2(1) before 1(2). C: 4(3) before 2(4).

3. Final Answer:

   [0, 1, 3, 2, 4] -> Option B

4. Quick Check:

   Dependencies respected in order [OK]

Hint: Tasks must come after all dependencies [OK]

Common Mistakes:

• Placing tasks before their dependencies
• Ignoring multiple dependencies per node
• Assuming any order is valid