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.

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…
• Adjacency list must not be null
• Adjacency list must not contain null sets
• adjacencyList size must equal vertexCount

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

Appendix: 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)