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

Time Complexity: Topological Sort Using DFS

O(n + 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 does the number of nodes and edges affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, stack, graph);
        }
    }
    stack.push(node);
}

void topologicalSort(int n, List<List<Integer>> graph) {
    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, visited, stack, graph);
    }
}
    

This code performs a topological sort on a directed graph using depth-first search (DFS).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of nodes (n) and edges (e) increase, the DFS explores all nodes and edges once.

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

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

Final Time Complexity

Time Complexity: O(n + e)

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

Common Mistake

[X] Wrong: "DFS visits each node multiple times, so complexity is higher than O(n + e)."

[OK] Correct: Each node is marked visited the first time it is explored, so DFS never revisits nodes, ensuring linear time.

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale and why DFS-based topological sort is efficient for dependency resolution.

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 graph?

easy

A. To find the shortest path between two nodes

B. To visit nodes in a way that all dependencies come before the node

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 processed first.

2. Step 2: Relation to dependencies

   In Topological Sort, DFS ensures nodes appear after all their dependencies (edges) are visited.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS post-order gives correct dependency order [OK]

Common Mistakes:

• Confusing DFS with shortest path algorithms
• Thinking DFS detects cycles in undirected graphs only
• Assuming DFS counts connected components in directed graphs

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

easy

A. visited[node] == true;

B. visited.add(node);

C. visited[node] = true;

D. visited[node] = false;

Solution

1. Step 1: Identify how visited nodes are tracked

   In Java, a boolean array is commonly used to mark nodes visited by setting visited[node] = true.

2. Step 2: Check each option

   visited[node] = true; correctly assigns true to visited[node]. visited.add(node); uses a method for collections, not arrays. visited[node] == true; compares but does not assign. visited[node] = false; wrongly sets false.

3. Final Answer:

   visited[node] = true; -> Option C

4. Quick Check:

   Assign true to mark visited [OK]

Hint: Use visited[node] = true to mark visited [OK]

Common Mistakes:

• Using comparison (==) instead of assignment (=)
• Using collection methods on arrays
• Setting visited to false instead of true

3. What is the output of the following Java code snippet performing topological sort using DFS on a graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1?

import java.util.*;

public class TopoSort {
    static void dfs(int node, boolean[] visited, Stack<Integer> stack, List graph) {
        visited[node] = true;
        for (int adj : graph.get(node)) {
            if (!visited[adj]) dfs(adj, visited, stack, graph);
        }
        stack.push(node);
    }

    public static void main(String[] args) {
        int V = 6;
        List graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

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

        while (!stack.isEmpty()) System.out.print(stack.pop() + " ");
    }
}

medium

A. 5 2 3 1 4 0

B. 4 5 2 3 1 0

C. 0 1 3 2 4 5

D. 5 4 2 3 1 0

Solution

1. Step 1: Understand graph and DFS order

   Graph edges: 5->2,5->0,4->0,4->1,2->3,3->1. DFS visits nodes, pushing after visiting all descendants.

2. Step 2: Trace DFS calls and stack pushes

   Start from node 0: no edges, push 0. Node 1: no edges, push 1. Node 2: visits 3, which visits 1 (already visited), push 3 then 2. Node 4: visits 0 and 1 (visited), push 4. Node 5: visits 2 and 0 (visited), push 5. Final stack (top to bottom): 5,4,2,3,1,0. Popping prints 5 4 2 3 1 0.

3. Final Answer:

   5 4 2 3 1 0 -> Option D

4. Quick Check:

   DFS post-order stack pop = 5 4 2 3 1 0 [OK]

Hint: Trace DFS post-order stack push and pop [OK]

Common Mistakes:

• Confusing push order with pop order
• Missing edges in graph construction
• Starting DFS from wrong nodes

4. Identify the error in this DFS-based topological sort code snippet and select the correct fix:

void dfs(int node, boolean[] visited, Stack<Integer> stack, List graph) {
    visited[node] = true;
    for (int adj : graph.get(node)) {
        if (visited[adj]) dfs(adj, visited, stack, graph);
    }
    stack.push(node);
}

medium

A. Change 'if (visited[adj])' to 'if (!visited[adj])' to visit unvisited nodes

B. Remove 'stack.push(node);' to avoid duplicates

C. Change 'visited[node] = true;' to 'visited[node] = false;' to reset visit

D. Change 'for (int adj : graph.get(node))' to 'for (int adj : graph)'

Solution

1. Step 1: Analyze the if condition in DFS

   The code calls dfs(adj) only if visited[adj] is true, meaning already visited nodes are revisited, causing infinite recursion or wrong order.

2. Step 2: Correct the condition to visit unvisited nodes

   It should call dfs(adj) only if visited[adj] is false, i.e., '!visited[adj]'. This prevents revisiting and ensures correct traversal.

3. Final Answer:

   Change 'if (visited[adj])' to 'if (!visited[adj])' to visit unvisited nodes -> Option A

4. Quick Check:

   Visit only unvisited nodes [OK]

Hint: DFS visits unvisited nodes only [OK]

Common Mistakes:

• Using visited[adj] instead of !visited[adj]
• Removing stack push causing incomplete order
• Incorrect loop over graph instead of adjacency list

5. Given a directed acyclic graph (DAG) with nodes 0 to 3 and edges: 0->1, 0->2, 1->2, 2->3, which of the following is a valid topological order using DFS-based topological sort? A topological order is a linear ordering where for every directed edge U->V, U comes before V.

hard

A. [0, 1, 2, 3]

B. [3, 2, 1, 0]

C. [1, 0, 2, 3]

D. [2, 0, 1, 3]

Solution

1. Step 1: Understand edges and constraints

   Edges: 0->1 means 0 before 1, 0->2 means 0 before 2, 1->2 means 1 before 2, 2->3 means 2 before 3.

2. Step 2: Check each option against constraints

   [0, 1, 2, 3]: 0 before 1, 1 before 2, 2 before 3 - valid.
   [3, 2, 1, 0]: 3 before 2 violates 2->3.
   [1, 0, 2, 3]: 1 before 0 violates 0->1.
   [2, 0, 1, 3]: 2 before 0 violates 0->2.

3. Final Answer:

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

4. Quick Check:

   Edges respected in order [OK]

Hint: Check edges U->V: U must come before V [OK]

Common Mistakes:

• Ignoring edge direction when ordering
• Reversing order without checking dependencies
• Assuming any order is valid if nodes appear once