Topological Sort Calculator
Order the nodes of a directed graph so every dependency comes first, with Kahn's algorithm, and print the cycle when no order exists.
Topological Sort Calculator
Order the nodes of a directed graph so every dependency comes first, with Kahn's algorithm, and print the cycle when no order exists.
How this page computes
In-degrees come from the edge list. A queue holds every node with in-degree zero; each round removes one from the queue, appends it to the order, and decrements its neighbours.
The comparison between the order length and the node count is the whole decision. On a mismatch the remaining nodes are walked along their still-incoming edges until a node repeats, which is the cycle printed in the refusal.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page orders the nodes of a directed graph so that every edge points forward. For A before B, A before C, B before D and C before D it prints A, B, C, D — and B, C, A, D would be equally valid, which is why the page names the tie-break it used.
A cycle has no such order, and the page prints the cycle it found instead of a partial list. That is the useful answer: a build graph or a course plan that loops needs the loop named.
How to use Topological Sort Calculator
Write one directed edge per line as "A B", meaning A must come before B. The weight column is optional and ignored, so a pasted weighted list still works.
Press Run for the order. Ties are broken by each node's first appearance in your list, so the same paste always prints the same order.
Kahn's algorithm, and the cycle it leaves behind
Count each node's in-degree — how many edges point at it. Every node with in-degree zero can go first; place one, subtract it from its neighbours' in-degrees, and any neighbour that reaches zero becomes available. Repeat until nothing is available.
If every node was placed, the order is valid. If some remain, each still has an incoming edge from another remaining node, so following those edges must eventually revisit a node: that closed walk is a cycle, and the page prints it.
What to Expect
Best for
- Ordering a build, a course plan or a set of dependent tasks
- Proving that a dependency graph has no loop
- Getting the loop named when one exists
Not ideal for
- Graphs with weights that matter, which is a shortest-path question
- Cyclic graphs that need a different structure, such as a condensation
- Undirected graphs, where no orientation is stated
What this tool keeps
- Every edge and its direction
What may need cleanup
- Nothing: the order or the cycle is final
Common errors
- A self-loop is refused, because no node can precede itself
- A cycle is reported with its nodes rather than as a failure message
Example use cases
- Order four build steps with two shared dependencies
- Detect a circular dependency in a task list
- Check a course prerequisite plan
Sample input
A before B, A before C, B before D, C before D
Sample output
topological order A, B, C, D with A the only source
Who this is for
- Build engineers ordering steps
- Students learning directed graphs
Frequently asked questions
Is the order unique?
Only when the graph forces it. A, B, C, D and B, C, A, D both satisfy the sample, and the page prints the first because it breaks ties by first appearance. Any printed order is valid.
What does a cycle look like?
The refusal names the nodes in order, such as A -> B -> C -> A. Removing or reversing one edge in that loop makes an order possible, and the page then prints one.
Does the weight column matter?
No. A topological order depends only on which edges exist and which way they point, so the third field is accepted and ignored so a weighted paste still runs.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.