Topological Sort Using DFS in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Topological Sort using DFS?

It visits nodes deeply first, then adds them to the order after all their dependencies are visited, ensuring that each node appears before nodes that depend on it.

beginner

In Topological Sort using DFS, when do we add a node to the result list?

We add a node to the result list only after visiting all its neighbors (dependencies) recursively.

intermediate

Why is Topological Sort only possible on Directed Acyclic Graphs (DAGs)?

Because cycles create circular dependencies, making it impossible to order nodes linearly without breaking dependency rules.

beginner

What data structure is commonly used to keep track of visited nodes in DFS for Topological Sort?

A boolean array or set is used to mark nodes as visited to avoid revisiting and infinite loops.

intermediate

How does the order of nodes in the final topological sort relate to the order they are added during DFS?

Nodes are added after visiting all dependencies, so the final order is the reverse of the order nodes are added during DFS.

What type of graph is required for Topological Sort using DFS?

A Directed Acyclic Graph (DAG)

B Undirected Graph

C Cyclic Graph

D Weighted Graph

Topological Sort works only on Directed Acyclic Graphs because cycles prevent a linear ordering.

When performing DFS for Topological Sort, when do you add a node to the result list?

A Before visiting its neighbors

B Randomly

C When first discovered

D After visiting all its neighbors

Nodes are added after all their neighbors are visited to ensure dependencies come first.

What happens if the graph contains a cycle during Topological Sort using DFS?

A The algorithm detects the cycle and fails

B The graph is converted to a tree

C The cycle is ignored

D The algorithm completes successfully

Cycles cause circular dependencies, so the algorithm must detect and handle them to avoid infinite loops.

Which data structure is typically used to store the final topological order in DFS?

A Queue

B Stack or list reversed at the end

C Hash Map

D Priority Queue

Nodes are pushed onto a stack or list after visiting neighbors, then reversed to get the correct order.

What is the time complexity of Topological Sort using DFS for a graph with V vertices and E edges?

A O(E^2)

B O(V^2)

C O(V + E)

D O(log V)

DFS visits each vertex and edge once, so the time complexity is linear in vertices plus edges.

Explain step-by-step how Topological Sort using DFS works on a Directed Acyclic Graph.

Think about visiting dependencies before the node itself.

Describe why cycles prevent Topological Sort and how DFS can detect them.

Consider how revisiting nodes during DFS signals a cycle.

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