Topological Sort Using DFS in DSA Java - Execution Trace

Concept Flow - Topological Sort Using DFS

Start DFS from unvisited node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor unvisited

↓

Recursive DFS on neighbor

↓

Add node to stack after neighbors

↓

Repeat for all nodes

↓

Pop all nodes from stack for topological order

Start DFS from each unvisited node, visit neighbors recursively, then add the node to a stack. Finally, pop nodes from the stack to get topological order.

Execution Sample

DSA Java

void dfs(int node) {
  visited[node] = true;
  for (int nbr : graph[node]) {
    if (!visited[nbr]) dfs(nbr);
  }
  stack.push(node);
}

This code visits nodes recursively and pushes them onto a stack after visiting all neighbors.

Execution Table

Step	Operation	Current Node	Visited Set	Stack State	Visual State
1	Start DFS at node 5	5	{}	[]	Graph nodes: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
2	Visit node 5	5	{5}	[]	Visited 5
3	Visit neighbor 2 of 5	2	{5}	[]	Going deeper from 5 to 2
4	Visit node 2	2	{5,2}	[]	Visited 2
5	Visit neighbor 3 of 2	3	{5,2}	[]	Going deeper from 2 to 3
6	Visit node 3	3	{5,2,3}	[]	Visited 3
7	Visit neighbor 1 of 3	1	{5,2,3}	[]	Going deeper from 3 to 1
8	Visit node 1	1	{5,2,3,1}	[]	Visited 1
9	No neighbors for 1, push 1	1	{5,2,3,1}	[1]	Stack: 1
10	Back to 3, all neighbors visited, push 3	3	{5,2,3,1}	[1,3]	Stack: 1 -> 3
11	Back to 2, all neighbors visited, push 2	2	{5,2,3,1}	[1,3,2]	Stack: 1 -> 3 -> 2
12	Back to 5, visit neighbor 0	0	{5,2,3,1}	[1,3,2]	Going deeper from 5 to 0
13	Visit node 0	0	{5,2,3,1,0}	[1,3,2]	Visited 0
14	No neighbors for 0, push 0	0	{5,2,3,1,0}	[1,3,2,0]	Stack: 1 -> 3 -> 2 -> 0
15	Back to 5, all neighbors visited, push 5	5	{5,2,3,1,0}	[1,3,2,0,5]	Stack: 1 -> 3 -> 2 -> 0 -> 5
16	Start DFS at node 4	4	{5,2,3,1,0}	[1,3,2,0,5]	Start DFS for unvisited node 4
17	Visit node 4	4	{5,2,3,1,0,4}	[1,3,2,0,5]	Visited 4
18	Visit neighbor 0 of 4 (already visited)	0	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 0, already visited
19	Visit neighbor 1 of 4 (already visited)	1	{5,2,3,1,0,4}	[1,3,2,0,5]	Skip 1, already visited
20	All neighbors visited, push 4	4	{5,2,3,1,0,4}	[1,3,2,0,5,4]	Stack: 1 -> 3 -> 2 -> 0 -> 5 -> 4
21	All nodes visited, pop stack for order	-	{5,2,3,1,0,4}	[1,3,2,0,5,4]	Topological order: 4,5,0,2,3,1
22	End	-	{5,2,3,1,0,4}	[]	All nodes processed, stack empty

💡 All nodes visited and pushed to stack; popping stack gives topological order.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 15	After Step 20	Final
visited	{}	{5}	{5,2}	{5,2,3}	{5,2,3,1}	{5,2,3,1,0}	{5,2,3,1,0,4}	{5,2,3,1,0,4}
stack	[]	[]	[]	[]	[1]	[1,3,2,0,5]	[1,3,2,0,5,4]	[]

Key Moments - 3 Insights

Why do we push the node onto the stack only after visiting all its neighbors?

Because in the execution_table at steps 9, 10, 11, and 15, nodes are pushed after all their neighbors are visited, ensuring dependencies come before dependents in the stack.

Why do we skip neighbors that are already visited?

As shown in steps 18 and 19, skipping visited neighbors prevents infinite loops and repeated work, ensuring each node is processed once.

How does popping the stack give the correct topological order?

At step 21, popping the stack reverses the order of insertion, so nodes with no dependencies come first, matching the topological order.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the state of the stack?

A [3]

B [1]

C []

D [1,3]

💡 Hint

Check the 'Stack State' column at step 9 in execution_table.

At which step does node 5 get pushed onto the stack?

A Step 11

B Step 20

C Step 15

D Step 21

💡 Hint

Look for when 'push 5' operation happens in the 'Operation' column.

If node 4 had an additional neighbor 2 (already visited), what would happen at step 18?

A Node 2 would be skipped as visited

B DFS would restart from node 2

C Node 2 would be visited again

D Stack would be cleared

💡 Hint

Refer to steps 18 and 19 where visited neighbors are skipped.

Concept Snapshot

Topological Sort Using DFS:
- Visit each unvisited node with DFS
- Recursively visit neighbors first
- Push node to stack after neighbors
- Pop stack for topological order
- Ensures dependencies come before dependents

Full Transcript

Topological Sort using DFS starts by visiting each node that hasn't been visited yet. For each node, we mark it visited and recursively visit all its neighbors. After visiting all neighbors, we push the node onto a stack. This ensures that nodes with dependencies are pushed after their dependencies. Once all nodes are processed, popping the stack gives the topological order. The execution table shows step-by-step how nodes are visited, neighbors explored, and nodes pushed to the stack. The variable tracker shows how the visited set and stack change over time. Key moments clarify why nodes are pushed after neighbors and why visited neighbors are skipped. The visual quiz tests understanding of stack state and order of operations. This method guarantees a valid topological order for directed acyclic graphs.

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