Topological Sort Using DFS in DSA Java - Build from Scratch

Topological Sort Using DFS

📖 Scenario: You are managing tasks in a project where some tasks must be done before others. To plan the order of tasks, you will use a method called topological sort using Depth-First Search (DFS).

🎯 Goal: Build a Java program that performs a topological sort on a directed graph representing task dependencies using DFS.

📋 What You'll Learn

Create a graph using adjacency lists with exact edges

Use a boolean array to track visited nodes

Implement DFS to explore nodes

Store the topological order in a stack

Print the topological order after DFS completes

💡 Why This Matters

🌍 Real World

Topological sort is used in project scheduling, build systems, and resolving dependencies where some tasks must happen before others.

💼 Career

Understanding topological sort and DFS is important for software engineers working on compilers, task schedulers, and dependency management tools.

1

Create the graph with adjacency lists

Create an integer variable V and set it to 6. Create an adjacency list array called graph of type ArrayList<Integer>[] with size V. Initialize each element of graph with a new ArrayList<Integer>(). Add edges exactly as follows: from 5 to 2, from 5 to 0, from 4 to 0, from 4 to 1, from 2 to 3, and from 3 to 1.

DSA Java

// Create graph with 6 vertices and add edges
// Your code here

Hint

Use a loop to initialize each element of graph with a new ArrayList<Integer>(). Then add edges using graph[from].add(to).

2

Create visited array and stack for order

Create a boolean array called visited with size V. Create a Stack<Integer> called stack to store the topological order.

DSA Java

import java.util.ArrayList;
import java.util.Stack;

public class TopologicalSortDFS {
    static int V = 6;
    static ArrayList[] graph = new ArrayList[V];

    public static void main(String[] args) {
        for (int i = 0; i ();
        }
        graph[5].add(2);
        graph[5].add(0);
        graph[4].add(0);
        graph[4].add(1);
        graph[2].add(3);
        graph[3].add(1);

        // Create visited array and stack
        // Your code here
    }
}

Hint

Use boolean[] visited = new boolean[V] and Stack<Integer> stack = new Stack<>().

3

Implement DFS function and call it for all nodes

Create a static method dfs with parameters int node, boolean[] visited, and Stack<Integer> stack. Inside dfs, mark visited[node] as true. For each neighbor in graph[node], if it is not visited, call dfs recursively. After visiting neighbors, push node onto stack. In main, use a for loop from 0 to V-1 and call dfs for nodes not visited.

DSA Java

import java.util.ArrayList;
import java.util.Stack;

public class TopologicalSortDFS {
    static int V = 6;
    static ArrayList[] graph = new ArrayList[V];

    public static void main(String[] args) {
        for (int i = 0; i ();
        }
        graph[5].add(2);
        graph[5].add(0);
        graph[4].add(0);
        graph[4].add(1);
        graph[2].add(3);
        graph[3].add(1);

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

        // Implement DFS calls for all nodes
        // Your code here
    }

    // Implement dfs method
    // Your code here
}

Hint

Define dfs to mark nodes visited, explore neighbors recursively, then push the node to stack. Call dfs for each unvisited node in main.

4

Print the topological order from the stack

After the DFS calls in main, use a while loop to pop elements from stack and print them separated by spaces on one line.

DSA Java

Hint

Pop from stack until empty and print each node followed by a space.

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