Topological Sort Using DFS in DSA Javascript - Execution Trace

Concept Flow - Topological Sort Using DFS

Start with all nodes

↓

Pick unvisited node

↓

DFS: Visit node

↓

For each neighbor

↓

If neighbor unvisited

↓

Recursive DFS on neighbor

↓

After all neighbors visited

↓

Add node to stack

↓

Repeat until all nodes visited

↓

Pop all nodes from stack for topological order

Start DFS from unvisited nodes, recursively visit neighbors, then add nodes to stack after visiting all neighbors. Finally, pop stack for topological order.

Execution Sample

DSA Javascript

function topoSort(graph) {
  const visited = new Set();
  const stack = [];
  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    stack.push(node);
  }
  for (const node in graph) {
    if (!visited.has(node)) dfs(node);
  }
  return stack.reverse();
}

Performs DFS on each unvisited node, pushes nodes to stack after visiting neighbors, then reverses stack for topological order.

Execution Table

Step	Operation	Current Node	Visited Set	Stack	Action Description
1	Start	-	{}	[]	Initialize visited set and stack
2	Pick node	A	{}	[]	Start DFS from node A
3	Visit node	A	{A}	[]	Mark A visited
4	Check neighbor	B	{A}	[]	Neighbor B not visited, DFS on B
5	Visit node	B	{A,B}	[]	Mark B visited
6	Check neighbor	C	{A,B}	[]	Neighbor C not visited, DFS on C
7	Visit node	C	{A,B,C}	[]	Mark C visited
8	Check neighbor	D	{A,B,C}	[]	Neighbor D not visited, DFS on D
9	Visit node	D	{A,B,C,D}	[]	Mark D visited
10	No neighbors	D	{A,B,C,D}	[]	D has no neighbors, push D to stack
11	Back to C	C	{A,B,C,D}	[D]	All neighbors visited, push C to stack
12	Back to B	B	{A,B,C,D}	[D,C]	All neighbors visited, push B to stack
13	Back to A	A	{A,B,C,D}	[D,C,B]	All neighbors visited, push A to stack
14	Pick node	E	{A,B,C,D}	[D,C,B,A]	Node E unvisited, start DFS on E
15	Visit node	E	{A,B,C,D,E}	[D,C,B,A]	Mark E visited
16	Check neighbor	F	{A,B,C,D,E}	[D,C,B,A]	Neighbor F not visited, DFS on F
17	Visit node	F	{A,B,C,D,E,F}	[D,C,B,A]	Mark F visited
18	No neighbors	F	{A,B,C,D,E,F}	[D,C,B,A]	F has no neighbors, push F to stack
19	Back to E	E	{A,B,C,D,E,F}	[D,C,B,A,F]	All neighbors visited, push E to stack
20	All nodes visited	-	{A,B,C,D,E,F}	[D,C,B,A,F,E]	DFS complete for all nodes
21	Reverse stack	-	{A,B,C,D,E,F}	[E,F,A,B,C,D]	Reverse stack for topological order

💡 All nodes visited, DFS complete, stack reversed for final topological order

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 13	After Step 19	Final
visited	{}	{A}	{A,B,C,D}	{A,B,C,D}	{A,B,C,D,E,F}	{A,B,C,D,E,F}
stack	[]	[]	[]	[D,C,B]	[D,C,B,A,F,E]	[E,F,A,B,C,D]

Key Moments - 3 Insights

Why do we add the node to the stack only after visiting all its neighbors?

Because in execution_table rows 10, 11, 12, and 13, nodes are pushed after all neighbors are visited, ensuring dependencies come before the node in the final order.

Why do we reverse the stack at the end?

As shown in step 21, nodes are pushed after visiting neighbors, so the stack has nodes in reverse topological order. Reversing it gives the correct order.

What happens if a node has no neighbors?

As in step 10 and 18, nodes with no neighbors are pushed immediately to the stack after being visited.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, which nodes are visited?

A {A, B, C, D}

B {A, B, C}

C {A, B}

D {}

💡 Hint

Check the 'Visited Set' column at step 9 in execution_table

At which step is node 'A' pushed to the stack?

A Step 10

B Step 11

C Step 13

D Step 21

💡 Hint

Look at the 'Stack' and 'Action Description' columns in execution_table rows 10-14

If we did not reverse the stack at the end, what would be the topological order?

A [E, F, A, B, C, D]

B [D, C, B, A, F, E]

C [A, B, C, D, E, F]

D [F, E, D, C, B, A]

💡 Hint

Check the 'Stack' column before reversal at step 20 in execution_table

Concept Snapshot

Topological Sort Using DFS:
- Visit each unvisited node with DFS
- Recursively visit neighbors first
- Push node to stack after neighbors
- Reverse stack for final order
- Works only on Directed Acyclic Graphs (DAGs)

Full Transcript

Topological Sort using DFS starts by visiting each node that has not been visited yet. For each node, we recursively visit all its neighbors before adding the node itself to a stack. This ensures that nodes appear after their dependencies in the stack. After all nodes are visited, we reverse the stack to get the correct topological order. The execution table shows step-by-step how nodes are visited, added to the visited set, and pushed to the stack. Key moments include why nodes are pushed after neighbors and why the stack is reversed at the end. The variable tracker shows how the visited set and stack change over time. This method works only on directed acyclic graphs to avoid cycles.

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