Topological Sort Using DFS in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Topological Sort on a Simple DAG

What is the output of the following Java code performing topological sort using DFS on the given graph?

DSA Java

import java.util.*;

public class Main {
    static void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> 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 = 4;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(2);
        graph.get(2).add(3);

        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() + " ");
        }
    }
}

A 3 2 1 0

B 0 1 2 3

C 0 2 1 3

D 1 0 2 3

💡 Hint

Remember that in DFS-based topological sort, nodes are pushed to stack after visiting all descendants.

The DFS visits nodes starting from 0, exploring 1 and 2 before 3. The stack ends up with 3 on top, then 2, then 1, then 0 at bottom. Popping gives 3 2 1 0.

🧠 Conceptual

intermediate

Understanding the Role of Stack in DFS Topological Sort

In DFS-based topological sort, why do we push the node onto the stack only after visiting all its adjacent nodes?

A To store nodes in the order they are first discovered

B To avoid revisiting nodes multiple times

C To ensure nodes are output in reverse order of completion, respecting dependencies

D To mark nodes as visited before exploring neighbors

💡 Hint

Think about the order in which nodes should appear to respect dependency directions.

Pushing nodes after visiting all neighbors ensures that dependent nodes come before the node itself in the final order, which is why popping from the stack gives a valid topological order.

🔧 Debug

advanced

Identify the Error in DFS Topological Sort Implementation

What error will occur when running this code snippet for topological sort using DFS?

DSA Java

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

A No error, code runs correctly

B StackOverflowError due to infinite recursion

C NullPointerException due to uninitialized graph

D ArrayIndexOutOfBoundsException due to invalid node index

💡 Hint

Check the condition that decides when to recurse on adjacent nodes.

The condition 'if (visited[adj])' recurses on already visited nodes, causing infinite recursion and eventually StackOverflowError.

❓ Predict Output

advanced

Output of Topological Sort on Graph with Multiple Independent Chains

What is the output of the following Java code performing topological sort using DFS on the given graph with two independent chains?

DSA Java

import java.util.*;

public class Main {
    static void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> 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<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(3).add(4);
        graph.get(4).add(5);

        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() + " ");
        }
    }
}

A 3 4 5 0 1 2

B 0 1 2 3 4 5

C 0 3 1 4 2 5

D 5 4 3 2 1 0

💡 Hint

Consider the order in which nodes are visited and pushed to the stack for independent chains.

DFS visits nodes from 0 to 5. It finishes chain 0->1->2 first, pushing 2,1,0, then visits chain 3->4->5 pushing 5,4,3. Popping stack gives 3 4 5 0 1 2.

🧠 Conceptual

expert

Detecting Cycles in Directed Graph Using DFS for Topological Sort

Which approach correctly detects a cycle in a directed graph during DFS-based topological sort?

A Use a queue to track nodes with zero incoming edges

B Check if a node is visited before starting DFS on it

C Count total edges and compare with nodes to find cycles

D Maintain a recursion stack to check if a node is visited again in the current DFS path

💡 Hint

Think about how to detect back edges during DFS traversal.

Using a recursion stack helps detect back edges indicating cycles. If a node is found in the recursion stack during DFS, a cycle exists.

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