TheAlgorithms/Java · error · IllegalStateException

Graph contains a cycle, topological sort not possible

Error message

Graph contains a cycle, topological sort not possible

What it means

Thrown by Kahn's algorithm when the number of processed vertices is less than the total vertex count. Kahn's algorithm repeatedly removes zero-in-degree vertices; if some vertices remain, they sit on a cycle, so a topological order is impossible. This is an `IllegalStateException` because the graph's structure, not the arguments, is the problem.

Source

Thrown at src/main/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithm.java:135

        ArrayList<E> answer = new ArrayList<>();
        int processedVertices = 0;

        while (!q.isEmpty()) {
            E current = q.poll();
            answer.add(current);
            processedVertices++;

            for (E adjacent : graph.getAdjacents(current)) {
                inDegree.put(adjacent, inDegree.get(adjacent) - 1);
                if (inDegree.get(adjacent) == 0) {
                    q.add(adjacent);
                }
            }
        }

        if (processedVertices != graph.getVertices().size()) {
            throw new IllegalStateException("Graph contains a cycle, topological sort not possible");
        }

        return answer;
    }
}

/**
 * A driver class that sorts a given graph in topological order using Kahn's algorithm.
 */
public final class KahnsAlgorithm {
    private KahnsAlgorithm() {
    }

    public static void main(String[] args) {
        // Graph definition and initialization
        AdjacencyList<String> graph = new AdjacencyList<>();
        graph.addEdge("a", "b");
        graph.addEdge("c", "a");

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Break the cycle in the input graph (remove or reverse the offending edge)
2. Detect and report the cycle (DFS/Tarjan cycle detection) before sorting
3. If cycles are expected in your domain, use a routine that handles them

Example fix

// before
List<E> order = KahnsAlgorithm.topoSort(graph); // throws on cyclic graph
// after
if (hasCycle(graph)) {
    reportCycle(graph);
} else {
    List<E> order = KahnsAlgorithm.topoSort(graph);
}

// Verify the graph is acyclic (DFS or Tarjan) before invoking the
// topological sort.

try {
    KahnsAlgorithm.topoSort(graph);
} catch (IllegalStateException e) {
    // graph has a cycle; report the offending edges
}

When it happens

Trigger: Calling the topological sort on a directed graph that contains at least one cycle — the queue empties before all vertices are emitted, so `processedVertices != graph.getVertices().size()`.

Common situations: Dependency graphs with circular dependencies (build/compile order, task scheduling); accidentally bidirectional edges in what should be a DAG; data import that introduces a loop.

Related errors

• Graph contains a negative weight cycle
• This graph contains a cycle. No linear ordering is possible.
• Number of vertices must be positive
• Edges list must not be null or empty
• Edge vertex out of range

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/ebc456f259e4e5f6. Report an issue: GitHub.