Topological Sort Using DFS in DSA C++ - Build from Scratch

Topological Sort Using DFS

📖 Scenario: You are managing tasks in a project where some tasks must be done before others. You want to find an order to do all tasks so that each task is done only after all its prerequisites are completed.

🎯 Goal: Build a program that uses Depth-First Search (DFS) to perform a topological sort on a directed graph representing task dependencies. The program will output the order to complete the tasks.

📋 What You'll Learn

Create a directed graph using an adjacency list with exact tasks and edges

Create a visited array to track visited tasks

Implement a DFS function to explore tasks

Use DFS to perform topological sort and store the order

Print the tasks in topological order

💡 Why This Matters

🌍 Real World

Topological sort is used in project management, build systems, and scheduling where tasks have dependencies.

💼 Career

Understanding topological sort and DFS is important for software engineers working on compilers, task schedulers, and dependency resolution.

1

Create the graph with tasks and dependencies

Create an adjacency list called graph as a vector of vectors of integers with size 6. Add edges exactly as follows: from task 5 to 2, from 5 to 0, from 4 to 0, from 4 to 1, from 2 to 3, and from 3 to 1.

DSA C++

# Create the graph adjacency list with 6 tasks and add edges
# Your code here

Hint

Use vector> graph(6); to create the graph. Use graph[from].push_back(to); to add edges.

2

Create a visited array to track tasks

Create a vector of booleans called visited with size 6 and initialize all values to false.

DSA C++

#include 
#include 
using namespace std;

int main() {
    vector> graph(6);
    graph[5].push_back(2);
    graph[5].push_back(0);
    graph[4].push_back(0);
    graph[4].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(1);

    // Create visited vector
    // Your code here

    return 0;
}

Hint

Use vector visited(6, false); to create the visited array.

3

Implement DFS function and perform topological sort

Define a function dfs that takes int node, vector>& graph, vector& visited, and vector& order. Mark node as visited. For each neighbor in graph[node], if not visited, call dfs recursively. After visiting neighbors, add node to order. In main, create a vector order. Loop through nodes 0 to 5, call dfs for unvisited nodes.

DSA C++

#include 
#include 
using namespace std;

void dfs(int node, vector>& graph, vector& visited, vector& order) {
    // Your code here
}

int main() {
    vector> graph(6);
    graph[5].push_back(2);
    graph[5].push_back(0);
    graph[4].push_back(0);
    graph[4].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(1);

    vector visited(6, false);

    // Your code here

    return 0;
}

Hint

Define dfs to mark nodes visited, explore neighbors recursively, then add node to order. In main, loop over all nodes and call dfs if not visited.

4

Print the topological order

Print the tasks in reverse order of the order vector separated by spaces on one line.

DSA C++

#include 
#include 
using namespace std;

void dfs(int node, vector>& graph, vector& visited, vector& order) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited, order);
        }
    }
    order.push_back(node);
}

int main() {
    vector> graph(6);
    graph[5].push_back(2);
    graph[5].push_back(0);
    graph[4].push_back(0);
    graph[4].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(1);

    vector visited(6, false);
    vector order;

    for (int i = 0; i < 6; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited, order);
        }
    }

    // Print tasks in topological order
    // Your code here

    return 0;
}

Hint

Print the order vector in reverse using a for loop and cout.

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