Java - Topological Sort

Topological sorting of a Directed Acyclic Graph (DAG) is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v.

Use Case Example

// Vertices = 6

// Edges: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1

Expected Topological Order:

4 5 2 3 1 0

Java Code (DFS Approach)

import java.util.*;

public class TopologicalSortDFS {

    public static void topologicalSort(int V, List<List<Integer>> adj) {

        boolean[] visited = new boolean[V];

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < V; i++) {

            if (!visited[i]) {

                dfs(i, visited, adj, stack);

            }

        }

        // Print topological order

        System.out.print("Topological Order: ");

        while (!stack.isEmpty()) {

            System.out.print(stack.pop() + " ");

        }

    }

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

        visited[node] = true;

        for (int neighbor : adj.get(node)) {

            if (!visited[neighbor]) {

                dfs(neighbor, visited, adj, stack);

            }

        }

        stack.push(node); // Push after visiting all descendants

    }

    public static void main(String[] args) {

        int V = 6;

        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < V; i++) {

            adj.add(new ArrayList<>());

        }

        // Directed edges

        adj.get(5).add(2);

        adj.get(5).add(0);

        adj.get(4).add(0);

        adj.get(4).add(1);

        adj.get(2).add(3);

        adj.get(3).add(1);

        topologicalSort(V, adj);

    }

}