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

Time Complexity: Topological Sort Using DFS

O(V^2)

Understanding Time Complexity

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

The question is: how does the number of steps grow when we have more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dfs(int node, int visited[], int stack[], int *top, int graph[][N], int n) {
    visited[node] = 1;
    for (int i = 0; i < n; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, visited, stack, top, graph, n);
        }
    }
    stack[(*top)++] = node;
}

void topologicalSort(int graph[][N], int n) {
    int visited[N] = {0};
    int stack[N];
    int top = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, stack, &top, graph, n);
        }
    }
}
    

This code performs a topological sort on a graph using Depth-First Search (DFS).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node once and scans the entire row of the adjacency matrix (checks all possible outgoing edges).
• How many times: Each node is visited once; from each node, the loop runs n times (once for each possible neighbor), totaling O(n^2).

How Execution Grows With Input

As the number of nodes grows, the work grows quadratically with nodes (independent of actual edges due to matrix representation).

Input Size	Approx. Operations
10 nodes	About 100 checks (10 nodes * 10 checks/node)
100 nodes	About 10,000 checks (100 * 100)
1000 nodes	About 1,000,000 checks (1000 * 1000)

Pattern observation: The operations grow quadratically with the number of nodes.

Final Time Complexity

Time Complexity: O(V^2)

This means the time grows quadratically with the number of nodes (V) in the graph. (For adjacency lists, it would be O(V + E).)

Common Mistake

[X] Wrong: "DFS takes O(V + E) time because each edge is checked once."

[OK] Correct: Although there appears to be a nested loop, no—in adjacency matrix, every node scans all V possible neighbors (including non-edges), so total work is O(V^2), not O(V + E).

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale, a key skill in many coding challenges and real projects.

Self-Check

"What if the graph is represented using adjacency lists instead of an adjacency matrix? 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 visit nodes in a way that all dependencies come before the node

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS to dependency order

   This ensures nodes appear after all their dependencies, which is the goal of topological sorting.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS ensures dependencies come before nodes in topological order [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking DFS detects cycles in undirected graphs here
• Mixing connected components 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 C?

easy

A. visited(node) = true;

B. visited[node] = 1;

C. visited[node] == true;

D. visited[node] = false;

Solution

1. Step 1: Understand C syntax for arrays

   In C, arrays use square brackets to access elements, so visited[node] is correct.

2. Step 2: Assigning visited status

   Assigning 1 marks the node as visited; '==' is comparison, not assignment; 'false' would mark unvisited.

3. Final Answer:

   visited[node] = 1; -> Option B

4. Quick Check:

   Use visited[node] = 1 to mark visited [OK]

Hint: Use visited[node] = 1 to mark visited in C arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Using '==' instead of '=' for assignment
• Assigning false instead of true/1 to mark visited

3. What is the output order of nodes after performing DFS-based topological sort on this graph?

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

Assume nodes are pushed to stack after visiting all neighbors and stack is printed top to bottom.

medium

A. [0, 2, 1, 3]

B. [3, 2, 1, 0]

C. [0, 1, 2, 3]

D. [3, 1, 2, 0]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then neighbors 1 then 2 (edge order). From 1 to 3, from 2 to 3 (visited).

2. Step 2: Push nodes to stack after visiting neighbors

   Push 3, then 1, then 3 already visited, then 2, then 0. Stack top to bottom: [3, 1, 2, 0].

3. Final Answer:

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

4. Quick Check:

   Stack top to bottom after DFS = [3, 1, 2, 0] [OK]

Hint: Push nodes after neighbors; output is stack top to bottom [OK]

Common Mistakes:

• Pushing nodes before visiting neighbors
• Confusing order of neighbors visited
• Printing stack bottom to top instead of top to bottom

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

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < adj[node].size(); i++) {
    int nbr = adj[node][i];
    if (!visited[nbr])
      dfs(nbr);
  }
  stack.push(node);
}

medium

A. Stack push should be before recursive calls

B. Missing base case for cycle detection

C. Using adj[node].size() is invalid in C

D. visited array should be initialized to 2 instead of 1

Solution

1. Step 1: Check syntax for adjacency list size in C

   adj[node].size() is C++ syntax; C does not support .size() method on arrays.

2. Step 2: Identify correct way to get adjacency list size in C

   In C, adjacency lists are usually arrays with separate size variables; .size() causes compile error.

3. Final Answer:

   Using adj[node].size() is invalid in C -> Option C

4. Quick Check:

   adj[node].size() is C++ only, not C [OK]

Hint: Use array length variables in C, not .size() method [OK]

Common Mistakes:

• Confusing C and C++ syntax for containers
• Ignoring cycle detection in topological sort
• Pushing nodes before recursive calls

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 order using DFS-based topological sort?

hard

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

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

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

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

Solution

1. Step 1: Analyze prerequisites from edges

   (u -> v means u before v): 5 before 2 and 0; 4 before 0 and 1; 2 before 3; 3 before 1.

2. Step 2: Check each option for prerequisite order

   [4, 5, 2, 3, 1, 0]: 4 before 0 and 1, 5 before 2 and 0, 2 before 3, 3 before 1, all correct.

3. Final Answer:

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

4. Quick Check:

   All edges respected in order D [OK]

Hint: Check each edge u->v: u appears before v in order [OK]

Common Mistakes:

• Ignoring edge directions in order
• Placing dependent nodes before their prerequisites
• Assuming any order with all nodes is valid