What is a topological sort?

It's an ordering of a directed graph's vertices such that for every directed edge from u to v, u appears before v in the ordering — only possible when the graph has no cycles.

How does Kahn's algorithm work?

It repeatedly finds a node with zero remaining incoming edges (no unprocessed prerequisites), removes it and adds it to the output order, then decreases the in-degree of its neighbors, repeating until every node is processed.

What happens if the graph has a cycle?

The algorithm gets stuck — some nodes will always have at least one incoming edge from within the cycle, so they're never removable, and the calculator reports that no valid topological order exists.

Is the topological order always unique?

No — when multiple nodes have zero incoming edges at the same time, any of them could go next, so a graph can have several valid topological orders. This calculator picks one consistently using alphabetical tie-breaking.

How is this different from Dijkstra's algorithm?

Dijkstra's algorithm finds shortest paths in a weighted graph; topological sort finds a valid processing order in a directed graph based purely on dependency structure, with no notion of edge weight or distance.

What does '->' mean in the edge input?

It indicates direction — A->B means there's a directed edge from A to B (A must come before B), unlike the undirected 'A-B' format used by this site's other graph tools.

How many nodes can this calculator handle?

This calculator supports up to 50 nodes, keeping Kahn's algorithm instant while covering the vast majority of hand-entered dependency graphs.

Where is topological sorting used in real life?

It's used in build systems and compilers (compiling files in dependency order), package managers (installing dependencies before the packages that need them), task schedulers, and spreadsheet formula evaluation order.

Topological Sort Calculator — Order Tasks by Their Dependencies

Our Topological Sort Calculator finds a valid ordering of a directed graph's nodes such that every edge points from an earlier node to a later one — exactly the ordering you need for scheduling dependent tasks — using Kahn's algorithm, and clearly reports when no such ordering exists because the graph contains a cycle.

Quick Answer

Enter your directed graph as an edge list to instantly find a valid topological order via Kahn's algorithm, or detect that a cycle makes ordering impossible.

Directed edges (comma-separated)

Enter directed edges as NodeA->NodeB, e.g. A->B, A->C, B->D.

How to Use the Topological Sort Calculator — Kahn's Algorithm Online

1
Enter your directed graph as a comma-separated edge list, e.g. A->B, A->C, B->D.
2
Click 'Calculate' to find a valid topological order.
3
Review the resulting order, or the cycle-detected message if no order exists.

Why Use Topological Sort Calculator — Kahn's Algorithm Online?

A topological sort arranges a directed acyclic graph's nodes into a line where every edge points forward — the exact structure needed to schedule tasks with dependencies, compile files in the right order, or resolve package installation order. Kahn's algorithm finds it directly: repeatedly remove any node with no remaining incoming edges and append it to the order, updating the remaining graph as you go. If the process runs out of removable nodes before every node is placed, the graph must contain a cycle, meaning no valid ordering exists at all — this calculator detects that case explicitly rather than returning a partial or incorrect order.

Frequently Asked Questions

Related Tools

Dijkstra's Shortest Path Calculator — Weighted Graphs Online

Find the shortest path and total distance between two nodes in a weighted graph using Dijkstra's algorithm. Free calculator with a simple edge-list input.

Adjacency Matrix Calculator — Build a Graph Matrix Online

Build and display the adjacency matrix of a graph from a simple edge-list input, along with its degree sequence. Free calculator, weighted or unweighted.

Hamiltonian Path Checker — Visit Every Node Once Online

Check whether a graph has a Hamiltonian path — a path visiting every node exactly once — via backtracking search. Free calculator, scoped to graphs of up to 10 nodes.