Why Topological Sort Using DFS in DSA C++?

The Big Idea

What if you could instantly find the perfect order for any set of tasks with tricky dependencies?

The Scenario

Imagine you have a list of tasks to do, but some tasks must be done before others. For example, you can't bake a cake before mixing the ingredients. If you try to figure out the order by writing it down on paper and checking each dependency manually, it quickly becomes confusing and messy.

The Problem

Manually checking each task's dependencies is slow and easy to mess up. You might forget a dependency or create a wrong order, causing delays or mistakes. As the number of tasks grows, this manual method becomes impossible to manage without errors.

The Solution

Topological Sort using DFS (Depth-First Search) helps automatically find a correct order of tasks that respects all dependencies. It explores each task and its prerequisites deeply, then lists tasks in a way that ensures all required tasks come before dependent ones.

Before vs After

✗ Before

vector<string> tasks = {"Bake", "Mix", "Preheat"};
// Manually reorder tasks to satisfy dependencies
// No clear method, prone to errors

✓ After

void dfs(int task, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& order) {
  visited[task] = true;
  for (int next : graph[task]) {
    if (!visited[next]) dfs(next, graph, visited, order);
  }
  order.push(task);
}

What It Enables

This method enables automatic, error-free ordering of tasks or steps where some must come before others, even in complex systems.

Real Life Example

In software development, compiling code requires compiling some files before others because of dependencies. Topological sort ensures the compiler processes files in the correct order without manual checks.

Key Takeaways

Manual ordering of dependent tasks is slow and error-prone.

Topological Sort with DFS finds a valid order automatically.

This helps manage complex dependencies easily and correctly.

Practice

1. What is the main purpose of using DFS in Topological Sort on a Directed Acyclic Graph (DAG)?

easy

A. To count the total number of nodes in the graph

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 all dependencies come before the node

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are processed first.

2. Step 2: Relation to dependencies in DAG

   In Topological Sort, DFS ensures nodes are ordered so that all dependencies (edges) come before the node itself.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node -> Option D

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS orders nodes so dependencies appear before dependents [OK]

Common Mistakes:

• Confusing DFS with BFS for topological order
• Thinking DFS finds shortest paths
• Assuming DFS detects cycles in undirected graphs here

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

easy

A. visited(node) = true;

B. visited[node] = true;

C. visited[node] == true;

D. visited[node] != false;

Solution

1. Step 1: Understand C++ syntax for arrays or vectors

   To mark a node visited, we assign true to visited[node] using = operator.

2. Step 2: Analyze options for correctness

   visited[node] = true; uses correct syntax: visited[node] = true; Options A, C, D use wrong syntax or comparison operators.

3. Final Answer:

   visited[node] = true; -> Option B

4. Quick Check:

   Assignment uses =, not == or function call [OK]

Hint: Use = to assign true to visited[node] in C++ [OK]

Common Mistakes:

• Using == instead of = for assignment
• Using parentheses instead of brackets for indexing
• Using != false which is confusing and incorrect here

3. What will be the output topological order of the following graph using DFS?

Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 0, 2, 3]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then 1 and 3, then backtrack and visit 2 and 3 (already visited). The order of finishing nodes is 3,1,2,0 reversed gives topological order.

2. Step 2: Determine topological order

   Reversing finishing times gives [0, 2, 1, 3].

3. Final Answer:

   [0, 2, 1, 3] -> Option C

4. Quick Check:

   DFS finishing order reversed = [0,2,1,3] [OK]

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

Common Mistakes:

• Not reversing the DFS finishing order
• Visiting nodes in wrong order
• Confusing edges direction

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

void dfs(int node, vector<bool> &visited, stack<int> &st, vector<int> adj[]) {
  visited[node] = true;
  for (auto x : adj[node]) {
    if (!visited[x])
      dfs(x, visited, st, adj);
  }
  st.push(node);
}

// Called for all nodes
for (int i = 0; i < n; i++) {
  if (!visited[i])
    dfs(i, visited, st, adj);
}

medium

A. No error; code correctly implements DFS topological sort

B. Visited array should be reset inside dfs

C. Stack should be replaced with queue

D. Nodes should be pushed to stack before recursive calls

Solution

1. Step 1: Analyze DFS function logic

   DFS marks node visited, recursively visits neighbors, then pushes node to stack after all neighbors processed.

2. Step 2: Check correctness of stack usage and visited array

   Stack is used to store nodes in finishing order, visited array is correctly used and not reset inside DFS.

3. Final Answer:

   No error; code correctly implements DFS topological sort -> Option A

4. Quick Check:

   DFS post-order push to stack is correct [OK]

Hint: Push node after recursion to stack for correct order [OK]

Common Mistakes:

• Pushing node before recursion causing wrong order
• Resetting visited inside DFS causing infinite loops
• Using queue instead of stack for topological order

5. Given a graph with edges:

5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological sort using DFS?

hard

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

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

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

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

Solution

1. Step 1: Analyze dependencies from edges

   5 -> 2, 5 -> 0 mean 5 before 2 and 0; 4 -> 0, 4 -> 1 mean 4 before 0 and 1; 2 -> 3 mean 2 before 3; 3 -> 1 mean 3 before 1. So 5 and 4 come before their successors.

2. Step 2: Validate options respecting dependencies

   [5, 4, 2, 3, 1, 0] respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. Others violate these orders.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order [OK]

Hint: Check all edges point forward in topological order [OK]

Common Mistakes:

• Ignoring edge directions
• Placing dependent nodes before dependencies
• Assuming any order is valid