Topological Sorting in Java

In the field of graph theory, Topological Sort is a fundamental algorithm used to produce a linear ordering of vertices in a Directed Acyclic Graph (DAG). For every directed edge $u \to v$, vertex $u$ must appear before vertex $v$ in the resulting sequence.

This concept is indispensable in real-world software engineering and system design. Common applications include:

• Task Scheduling: Determining the order of operations where certain tasks depend on the completion of others.
• Dependency Resolution: Managing package dependencies in build systems like Maven, Gradle, or npm.
• Course Prerequisites: Organizing academic curricula where specific courses must be completed before moving to advanced levels.
• Instruction Scheduling: Optimizing the execution order of instructions in compilers.

The Critical Requirement: Acyclic Nature

It is vital to note that a topological sort is only possible if the graph is a DAG. If a graph contains a cycle (e.g., $A \to B$, $B \to C$, and $C \to A$), a valid topological ordering cannot exist because the dependencies are circular, creating a logical deadlock.

Furthermore, a topological sort is not necessarily unique. Depending on the structure of the graph, multiple valid sequences may exist. As long as all edge constraints are respected, any valid permutation is considered a correct answer.

Implementation Strategy 1: Kahn's Algorithm (BFS-based)

Kahn's algorithm is an intuitive approach based on the concept of in-degrees. The in-degree of a vertex is the number of incoming edges directed toward it. A vertex with an in-degree of 0 has no dependencies and can be processed immediately.

The Logic

1. Calculate In-degrees: Traverse the graph to count the in-degree for every vertex.
2. Initialize a Queue: Add all vertices with an in-degree of 0 to a queue.
3. Process the Queue:
   • Remove a vertex from the queue and add it to the topological order list.
   • For every neighbor of this vertex, decrement its in-degree by 1 (simulating the removal of the edge).
   • If a neighbor's in-degree drops to 0, add it to the queue.
4. Cycle Detection: If the final list contains fewer vertices than the total number of vertices in the graph, the graph contains at least one cycle.

Java Implementation

import java.util.*;

public class TopologicalSortKahn {
    /**
     * Performs topological sort using Kahn's Algorithm.
     * @param n The number of vertices.
     * @param edges A 2D array representing directed edges [u, v].
     * @return A list representing the topological order.
     * @throws IllegalStateException if a cycle is detected.
     */
    public static List<Integer> topoSort(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        int[] indegree = new int[n];
        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            graph.get(u).add(v);
            indegree[v]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);

            for (int v : graph.get(u)) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        if (order.size() != n) {
            throw new IllegalStateException("Cycle detected: Topological sort is impossible.");
        }
        return order;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {
            {5, 2}, {5, 0}, {4, 0},
            {4, 1}, {2, 3}, {3, 1}
        };
        try {
            System.out.println("Kahn's Order: " + topoSort(n, edges));
        } catch (IllegalStateException e) {
            System.err.println(e.getMessage());
        }
    }
}

Implementation Strategy 2: DFS-based Approach

The Depth-First Search (DFS) approach relies on the properties of post-order traversal. By exploring as deep as possible along each branch before backtracking, we can determine the "end" of a dependency chain.

The Logic

To implement this efficiently and detect cycles, we use a three-state marking system for each vertex:

• State 0 (Unvisited): The vertex has not been encountered yet.
• State 1 (Visiting): The vertex is currently in the recursion stack (we are exploring its neighbors).
• State 2 (Visited): The vertex and all its descendants have been fully processed.

If we encounter a neighbor that is currently in State 1, we have found a back-edge, which indicates a cycle. Once a vertex is fully processed (reaches State 2), we add it to a list. The final topological order is the reverse of this list.

Java Implementation

import java.util.*;

public class TopologicalSortDFS {
    private static List<List<Integer>> graph;
    private static int[] state; // 0: Unvisited, 1: Visiting, 2: Visited
    private static List<Integer> order;
    private static boolean hasCycle;

    /**
     * Performs topological sort using DFS.
     * @param n The number of vertices.
     * @param edges A 2D array representing directed edges [u, v].
     * @return A list representing the topological order.
     * @throws IllegalStateException if a cycle is detected.
     */
    public static List<Integer> topoSort(int n, int[][] edges) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
        }

        state = new int[n];
        order = new ArrayList<>();
        hasCycle = false;

        for (int i = 0; i < n; i++) {
            if (state[i] == 0) {
                dfs(i);
            }
        }

        if (hasCycle) {
            throw new IllegalStateException("Cycle detected: Topological sort is impossible.");
        }

        // The topological order is the reverse of the post-order traversal
        Collections.reverse(order);
        return order;
    }

    private static void dfs(int u) {
        state[u] = 1; // Mark as Visiting
        for (int v : graph.get(u)) {
            if (state[v] == 1) {
                hasCycle = true; // Found a back-edge (cycle)
                return;
            }
            if (state[v] == 0) {
                dfs(v);
            }
            if (hasCycle) return;
        }
        state[u] = 2; // Mark as Visited
        order.add(u);
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] edges = {
            {5, 2}, {5, 0}, {4, 0},
            {4, 1}, {2, 3}, {3, 1}
        };
        try {
            System.out.println("DFS Order: " + topoSort(n, edges));
        } catch (IllegalStateException e) {
            System.err.println(e.getMessage());
        }
    }
}

Complexity Analysis

Both Kahn's algorithm and the DFS-based approach share the same asymptotic complexity:

• Time Complexity: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges. Each vertex is visited once, and each edge is traversed exactly once.
• Space Complexity: $O(V + E)$. This accounts for the storage of the adjacency list, the in-degree array (Kahn's), the state array (DFS), and the recursion stack (DFS).

Summary and Practical Considerations

Choosing between Kahn's algorithm and DFS depends on your specific requirements:

Pro-Tip: If your application requires the lexicographically smallest topological sort (e.g., if multiple tasks can be done, always pick the one with the smallest ID), simply replace the ArrayDeque in Kahn's algorithm with a PriorityQueue<Integer>. This ensures that among all nodes with an in-degree of 0, the one with the smallest value is always processed next.