Topological Sort Using DFS in DSA Javascript

Mental Model

We visit each task and all tasks that depend on it first, then add the task to the order. This way, dependencies come before the tasks that need them.

Analogy: Imagine you have to finish homework problems, but some problems need answers from others first. You solve the ones with no dependencies first, then move on to the ones that depend on them.

Graph:
A -> B -> C
↑
D

We want an order like D -> A -> B -> C where each arrow means 'must come before'.

Dry Run Walkthrough

Input: Graph with edges: A->B, B->C, D->A

Goal: Find an order to do tasks so that each task comes after all tasks it depends on

Step 1: Start DFS from node D

Visited: D
Stack: []

Why: We pick a node to start the DFS traversal

Step 2: From D, DFS visits A

Visited: D, A
Stack: []

Why: We must finish A and its successors before adding D

Step 3: From A, DFS visits B

Visited: D, A, B
Stack: []

Why: B depends on A, so we explore B next

Step 4: From B, DFS visits C

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

Why: C depends on B, so we explore C next

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

Stack: [C]

Why: No more dependencies, so C can be placed last

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All successors of B done, add B

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All successors of A done, add A

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All successors of D done, add D

Result:

Stack reversed gives order: D -> A -> B -> C

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjList = new Map();
    for (const v of vertices) {
      this.adjList.set(v, []);
    }
  }

  addEdge(u, v) {
    this.adjList.get(u).push(v);
  }

  topologicalSort() {
    const visited = new Set();
    const stack = [];

    const dfs = (node) => {
      visited.add(node); // mark node visited
      for (const neighbor of this.adjList.get(node)) {
        if (!visited.has(neighbor)) {
          dfs(neighbor); // visit successors first
        }
      }
      stack.push(node); // add node after successors
    };

    for (const vertex of this.vertices) {
      if (!visited.has(vertex)) {
        dfs(vertex); // start DFS if not visited
      }
    }

    return stack.reverse(); // reverse to get correct order
  }
}

// Driver code
const vertices = ['A', 'B', 'C', 'D'];
const graph = new Graph(vertices);
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 current node as visited to avoid repeats

for (const neighbor of this.adjList.get(node)) { if (!visited.has(neighbor)) { dfs(neighbor); } }

visit all successors before current node

stack.push(node); // add node after dependencies

add node to stack after all successors are processed

for (const vertex of this.vertices) { if (!visited.has(vertex)) { dfs(vertex); } }

start DFS from all unvisited nodes to cover entire graph

return stack.reverse(); // reverse to get correct order

reverse stack to get topological order

Output

D -> A -> B -> C

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

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

vs Alternative: Compared to Kahn's algorithm which uses queue and in-degree counts, DFS uses recursion and stack but both have same time complexity

Edge Cases

Empty graph

Returns empty order without errors

DSA Javascript

for (const vertex of this.vertices) { if (!visited.has(vertex)) { dfs(vertex); } }

Graph with single node and no edges

Returns list with that single node

DSA Javascript

stack.push(node); // add node after dependencies

Graph with disconnected components

Processes each component separately and combines orders

DSA Javascript

for (const vertex of this.vertices) { if (!visited.has(vertex)) { dfs(vertex); } }

When to Use This Pattern

When you need to order tasks with dependencies and detect a sequence that respects all dependencies, use topological sort with DFS to explore dependencies first.

Common Mistakes

Mistake: Adding the node to the order before visiting its successors
Fix: Add the node to the stack only after all its successors have been visited

Mistake: Not marking nodes as visited, causing infinite loops
Fix: Use a visited set to track nodes already processed

Summary

It finds an order of tasks so that each task comes after all tasks it depends on.

Use it when you have tasks with dependencies and need a valid sequence to complete them.

The key is to visit all dependencies first before adding the task to the order.

Practice

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

easy

A. To count the number of connected components

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To visit nodes in a way that ensures dependencies come before dependents

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before it is processed.

2. Step 2: Relate DFS order to dependencies

   In Topological Sort, nodes are added after visiting all their dependencies, so dependencies come before dependents.

3. Final Answer:

   To visit nodes in a way that ensures dependencies come before dependents -> Option D

4. Quick Check:

   DFS ensures dependency order = A [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

• Confusing DFS with BFS for topological sorting
• Thinking DFS finds shortest paths
• Mixing cycle detection with topological order

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in JavaScript?

easy

A. visited = node;

B. visited.push(node);

C. visited[node] = true;

D. visited[node] == true;

Solution

1. Step 1: Understand visited marking in DFS

   Visited is usually an array or object where each node's visited status is stored as a boolean.

2. Step 2: Correct syntax for marking visited

   Assigning true to visited[node] marks that node visited; using '==' is comparison, not assignment.

3. Final Answer:

   visited[node] = true; -> Option C

4. Quick Check:

   Assign true to visited[node] = A [OK]

Hint: Use assignment (=), not comparison (==), to mark visited [OK]

Common Mistakes:

• Using '==' instead of '=' for assignment
• Using push on visited array instead of index assignment
• Overwriting visited variable instead of marking node

3. What will be the output of the following code snippet performing topological sort using DFS on the graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1?

const graph = {
  5: [2, 0],
  4: [0, 1],
  2: [3],
  3: [1],
  0: [],
  1: []
};

const visited = {};
const stack = [];

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

for (const node in graph) {
  if (!visited[node]) dfs(node);
}

console.log(stack.reverse());

medium

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

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

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

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

Solution

1. Step 1: Perform DFS and track stack push order

   DFS visits nodes deeply, pushing nodes after visiting neighbors. For node 5: visits 2, then 3, then 1, then 0; for node 4: visits 0 and 1. Stack push order is [1,3,2,0,5,4] reversed to [4,5,0,2,3,1].

2. Step 2: Reverse stack to get topological order

   Reversing stack gives [4, 5, 0, 2, 3, 1], which respects dependencies.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Not reversing the stack before output
• Visiting nodes in wrong order due to object key iteration
• Confusing push order with final topological order

4. Identify the bug in this DFS-based topological sort code snippet:

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

const graph = {0: [1], 1: [2], 2: []};
const visited = {};
const stack = [];
for (const node in graph) {
  dfs(node, graph, visited, stack);
}
console.log(stack.reverse());

medium

A. No bug; code works correctly

B. Visited check missing before recursive call

C. Stack should be cleared before DFS

D. Visited should be reset inside DFS function

Solution

1. Step 1: Analyze visited check and recursion

   The code checks if node is visited before recursion, preventing repeated visits.

2. Step 2: Confirm stack usage and output

   Nodes are pushed after visiting neighbors, and stack is reversed for correct order.

3. Final Answer:

   No bug; code works correctly -> Option A

4. Quick Check:

   No bug; code works correctly = C [OK]

Hint: Check visited before recursion to avoid repeats [OK]

Common Mistakes:

• Calling dfs without visited check causing infinite recursion
• Not reversing stack before output
• Resetting visited inside DFS causing wrong results

5. Given a directed graph with nodes and edges, how can you modify the DFS-based topological sort to detect if the graph has a cycle?

hard

A. Use an extra recursion stack to track nodes in the current DFS path and detect back edges

B. Count the number of nodes visited and compare with total nodes

C. Sort nodes by their degree before DFS

D. Run BFS instead of DFS to detect cycles

Solution

1. Step 1: Understand cycle detection in DFS

   Cycle exists if a node is visited again in the current DFS path (back edge).

2. Step 2: Use recursion stack to track current path

   Maintain a recursion stack array marking nodes currently in DFS call; if a neighbor is in recursion stack, cycle detected.

3. Final Answer:

   Use an extra recursion stack to track nodes in the current DFS path and detect back edges -> Option A

4. Quick Check:

   Recursion stack detects cycles = D [OK]

Hint: Track recursion stack to find back edges indicating cycles [OK]

Common Mistakes:

• Only using visited array without recursion stack
• Trying to detect cycles by node count mismatch
• Using BFS without proper cycle detection logic