DFS and Topological Sort in Graphs

Depth First Search (DFS) is a graph traversal technique where we explore as far as possible along each branch before backtracking. Topological sort is a special ordering of nodes in a Directed Acyclic Graph (DAG) where every directed edge u → v means u appears before v in the ordering.

Core Idea

• DFS explores deep paths before backtracking
• Topological sort is only valid for DAGs
• DFS postorder (finish time) gives reverse topological order
• Cycle detection is mandatory before topo sort

Graph Used in Example

We use the following directed graph:

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

DFS Traversal (Starting from Node 0)

DFS is a traversal technique. One valid DFS order depends on adjacency list ordering. If we start from 0 and choose 2 first, we get one valid traversal.

• 0 → 2 → 3 → 1 → 4 → 5
• OR 0 → 3 → 1 → 2 → 4 → 5 (depends on adjacency order)

DFS Java Code (Graph Traversal)

import java.util.*;

public class DFSGraph {

    static void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, adj);
            }
        }
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        adj.get(0).add(3);
        adj.get(0).add(2);
        adj.get(2).add(3);
        adj.get(2).add(1);
        adj.get(3).add(1);
        adj.get(4).add(1);
        adj.get(4).add(5);
        adj.get(5).add(1);

        boolean[] visited = new boolean[n];

        dfs(0, visited, adj);
    }
}

What DFS Code is Doing

• Marks node as visited
• Prints node when first visited
• Recursively visits neighbors
• Backtracks when no unvisited neighbor remains

Topological Sort Concept (DFS Method)

Topological sort using DFS is based on finishing time. Instead of printing when we visit a node, we push it to a stack after all its neighbors are processed.

• Visit node
• Explore all outgoing edges
• Push node to stack after completion
• Reverse stack for final order

Topological Sort Java Code (DFS Based)

import java.util.*;

public class TopoSortDFS {

    static void dfs(int node, boolean[] visited, Stack<Integer> stack, List<List<Integer>> adj) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, stack, adj);
            }
        }

        stack.push(node);
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        adj.get(0).add(3);
        adj.get(0).add(2);
        adj.get(2).add(3);
        adj.get(2).add(1);
        adj.get(3).add(1);
        adj.get(4).add(1);
        adj.get(4).add(5);
        adj.get(5).add(1);

        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, visited, stack, adj);
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

Why DFS Topological Sort Works

• A node is pushed only after all dependencies are processed
• So dependent nodes appear earlier in stack
• Reversing stack gives correct dependency order
• Ensures u → v means u comes before v

Cycle Detection Requirement

Topological sort only works if the graph has no cycles. If a cycle exists, ordering is impossible.

• Cycle makes dependency circular
• No valid ordering exists
• DFS can be extended using recursion stack to detect cycles

Fast Exam Tricks

• DFS = Go deep first, then backtrack
• Topological sort = DFS + reverse finishing order
• If cycle exists → NO topo sort
• Stack order always gives reversed dependency flow
• Always draw dependency arrows before solving

DFS vs Topological Sort Difference

• DFS = traversal (visit nodes)
• Topological sort = ordering (dependency resolution)
• DFS prints on visit
• Topological pushes on finish

Final Summary

• DFS explores nodes deeply before backtracking
• Topological sort is DFS with postorder stack
• Works only on DAGs (no cycles)
• Cycle detection is mandatory
• Java implementation uses recursion + stack