Topological Sort Using DFS in DSA Java

Mental Model

We visit each task and all tasks depending on it before marking it done, so tasks come out in order of dependencies.

Analogy: Imagine you have to finish homework problems where some problems need others done first. You start with a problem, do all its prerequisites first, then do it last.

Graph:
A -> B -> C
↑
D

Topological order means tasks arranged so every arrow points forward.

Dry Run Walkthrough

Input: Graph with edges: A->B, B->C, D->A

Goal: Find an order to do tasks so all dependencies come before the task itself

Step 1: Start DFS at node D

Visited: D
Stack: []

Why: We pick an unvisited node to begin exploring dependencies

Step 2: From D, visit A

Visited: D, A
Stack: []

Why: D depends on A, so we must visit A before finishing D

Step 3: From A, visit B

Visited: D, A, B
Stack: []

Why: A depends on B, so visit B first

Step 4: From B, visit C

Visited: D, A, B, C
Stack: []

Why: B depends on C, so visit C first

Step 5: C has no dependencies, add C to stack

Stack: [C]

Why: No more dependencies, so C can be done now

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All dependencies of B done, so B can be done

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All dependencies of A done, so A can be done

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All dependencies of D done, so D can be done

Result:

Stack (topological order): D -> A -> B -> C

Annotated Code

DSA Java

import java.util.*;

class Graph {
    private final int vertices;
    private final Map<Character, List<Character>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        this.adjList = new HashMap<>();
    }

    public void addEdge(char from, char to) {
        adjList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        adjList.putIfAbsent(to, new ArrayList<>());
    }

    private void dfs(char node, Set<Character> visited, Deque<Character> stack) {
        visited.add(node); // mark node visited
        for (char neighbor : adjList.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, visited, stack); // visit dependencies first
            }
        }
        stack.push(node); // add node after dependencies
    }

    public List<Character> topologicalSort() {
        Set<Character> visited = new HashSet<>();
        Deque<Character> stack = new ArrayDeque<>();

        for (char node : adjList.keySet()) {
            if (!visited.contains(node)) {
                dfs(node, visited, stack); // start DFS if unvisited
            }
        }

        List<Character> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop()); // pop from stack to get order
        }
        return result;
    }

    public static void main(String[] args) {
        Graph g = new Graph(4);
        g.addEdge('A', 'B');
        g.addEdge('B', 'C');
        g.addEdge('D', 'A');

        List<Character> order = g.topologicalSort();
        for (char c : order) {
            System.out.print(c + " ");
        }
        System.out.println();
    }
}

visited.add(node); // mark node visited

mark current node as visited to avoid revisiting

for (char neighbor : adjList.get(node)) { if (!visited.contains(neighbor)) { dfs(neighbor, visited, stack); } }

recursively visit all dependencies before current node

stack.push(node); // add node after dependencies

add node to stack only after all dependencies are processed

for (char node : adjList.keySet()) { if (!visited.contains(node)) { dfs(node, visited, stack); } }

start DFS from all unvisited nodes to cover entire graph

while (!stack.isEmpty()) { result.add(stack.pop()); }

pop nodes from stack to get topological order

Output

D A B C 

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for visited set and recursion stack in worst case

vs Alternative: Compared to Kahn's BFS approach which also runs in O(V + E), DFS uses recursion and stack, which can be simpler to implement but may risk stack overflow on very deep graphs

Edge Cases

Empty graph with no nodes

Returns empty order without errors

DSA Java

for (char node : adjList.keySet()) { if (!visited.contains(node)) { dfs(node, visited, stack); } }

Graph with single node and no edges

Returns list with that single node

DSA Java

stack.push(node); // add node after dependencies

Graph with disconnected components

Processes each component separately and returns combined order

DSA Java

for (char node : adjList.keySet()) { if (!visited.contains(node)) { dfs(node, visited, stack); } }

When to Use This Pattern

When you need to order tasks with dependencies and detect a valid sequence, use topological sort with DFS to explore dependencies deeply before ordering.

Common Mistakes

Mistake: Adding the node to the order before visiting its dependencies
Fix: Add the node to the stack only after all its neighbors (dependencies) have been visited

Mistake: Not marking nodes as visited, causing infinite recursion
Fix: Mark nodes as visited immediately when starting DFS on them

Summary

It orders tasks so that each task comes after all tasks it depends on.

Use it when you have tasks with dependencies and need a valid execution order.

The key is to visit all dependencies first before adding the task to the order.

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