Topological Sort Using DFS in DSA C++ - Time & Space Complexity

Time Complexity: Topological Sort Using DFS

O(V + E)

Understanding Time Complexity

We want to understand how the time needed to perform topological sort using DFS changes as the graph size grows.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void topoSort(int V, vector<int> adj[]) {
    vector<bool> visited(V, false);
    stack<int> st;
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            dfs(i, adj, visited, st);
        }
    }
}
    

This code performs a topological sort on a directed graph using DFS by visiting each node and its neighbors recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node and explores all its neighbors.
• How many times: Each node is visited once, and each edge is checked once during the DFS calls.

How Execution Grows With Input

As the number of nodes (V) and edges (E) increase, the DFS explores more nodes and edges.

Input Size (V, E)	Approx. Operations
10 nodes, 15 edges	About 25 operations (visiting nodes + edges)
100 nodes, 200 edges	About 300 operations
1000 nodes, 5000 edges	About 6000 operations

Pattern observation: The work grows roughly proportional to the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time grows linearly with the total number of nodes plus edges in the graph.

Common Mistake

[X] Wrong: "DFS visits each node multiple times, so time is O(V * E)."

[OK] Correct: Each node is marked visited and processed only once, so edges and nodes are checked only once in total.

Interview Connect

Understanding this time complexity helps you explain how efficient graph algorithms work and shows you can analyze recursive traversals clearly.

Self-Check

"What if the graph was represented using an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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