DFS and Topological Sort in Graphs (Complete Deep Guide with Java Code, Intuition, and Interview Prep)

Complete deep explanation of DFS and Topological Sort including intuition, step-by-step dry runs, cycle detection, Kahn’s algorithm, and production-ready Java code.

Topological Sort (DFS + Kahn) Deep Explanation

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, node u appears before v in the ordering. It is widely used in scheduling, dependency resolution, and build systems.

Key Idea

  • Graph must be a DAG (no cycles allowed)
  • DFS produces reverse finishing order
  • Kahn’s algorithm uses in-degree processing
  • Both approaches give valid topological order

Given Graph

0 → 3, 2
2 → 3, 1
3 → 1
4 → 1, 5
5 → 1

DFS Topological Sort Idea

In DFS-based topological sort, we do NOT add a node when we visit it. Instead, we add it AFTER all its neighbors are processed (postorder traversal). This ensures dependencies come first.

  • Visit node
  • Recursively visit all neighbors
  • Push node to stack after recursion ends
  • Reverse stack for final answer

DFS Dry Run (Starting from 0)

Assume adjacency order: 0→2 first, 2→3 first.

  • 0 → 2 → 3 → 1 (deep path)
  • Push 1 first
  • Then 3
  • Then 2
  • Then 0
  • Remaining nodes: 4 → 5 → 1

Final DFS Stack

[1, 3, 2, 0, 5, 4]

Final Topological Order (After Reverse)

4 → 5 → 0 → 2 → 3 → 1

Why DFS Topological Sort Works

  • A node is placed after all its dependencies
  • Postorder ensures correct dependency resolution
  • Reversing stack gives correct ordering
  • Ensures u → v means u appears before v

Kahn’s Algorithm (BFS Approach)

Kahn’s algorithm works by repeatedly removing nodes with in-degree 0 and updating neighbors.

  • Compute in-degree of all nodes
  • Push all 0 in-degree nodes into queue
  • Remove node, reduce neighbors' in-degree
  • Add new 0 in-degree nodes to queue
  • Repeat until queue is empty

In-Degree Table

0 → 0
2 → 1
3 → 2
1 → 4
4 → 0
5 → 1

Kahn’s Output

0 → 4 → 2 → 5 → 3 → 1

DFS vs Kahn Comparison

  • DFS uses recursion and stack
  • Kahn uses queue (BFS)
  • DFS is postorder based
  • Kahn is in-degree based
  • Kahn detects cycle more easily

Cycle Detection

Topological sort is only possible if there is no cycle in the graph. DFS cycle detection uses recursion stack tracking.

  • visited[] tracks visited nodes
  • recStack[] tracks current path
  • If node appears in recStack → cycle exists
  • Cycle means topo sort is impossible

Fast Exam Tricks

  • DFS topo = reverse of finishing order
  • Always push after recursion ends
  • Kahn starts from in-degree 0 nodes
  • Cycle → no topological order
  • DFS order ≠ topo order (important confusion)

Final Summary

  • DFS explores deep paths first
  • Topological sort depends on postorder DFS
  • Kahn’s algorithm uses BFS + in-degree
  • Both give valid DAG ordering
  • Cycle detection is mandatory for correctness