Ordering condition
position(u) < position(v)
This inequality must hold for every edge u → v.
Topological Sort Calculator for Directed Acyclic Graphs
Enter a directed graph
Private by design: graph data is processed on this device. It is not uploaded, saved, or added to the page URL.
Advertisement
What is a topological sort?
A topological order is a linear ordering of a directed graph's vertices such that every edge points forward in the order. For every directed edge u → v, vertex u must appear before v. A topological ordering exists exactly when the directed graph is acyclic.
Source vertex
indegree(v) = 0
A source has no remaining prerequisite and can be selected next by Kahn's algorithm.
Time complexity
O(|V| + |E|)
The underlying algorithm visits each vertex and directed edge; displayed tie sorting adds a small ordering cost.
How Kahn's algorithm works
1. Count indegrees
Count the incoming edges for every vertex. Put every zero-indegree vertex into the available set.
2. Select a source
Choose one available vertex using the selected tie-breaker and append it to the topological order.
3. Remove outgoing edges
Decrease the indegree of each destination reached from the selected vertex. Add any destination that reaches zero.
4. Detect a cycle
If vertices remain but none has indegree zero, those remaining dependencies contain a directed cycle, so no topological order exists.
The calculator also reports uniqueness. The order is unique exactly when there is only one zero-indegree choice at every selection step. If a tie occurs, at least two valid topological orders exist.
Topological sort example
Suppose a meal has five tasks and these dependencies:
- Plan → Shop and Plan → Prep
- Shop → Cook and Prep → Cook
- Cook → Serve
Plan is initially the only zero-indegree task. After Plan is removed, Shop and Prep are both available, so their relative order is not forced. With input-order tie-breaking, one valid result is Plan → Shop → Prep → Cook → Serve. The ordering is not unique because Prep could appear before Shop.
The dependency levels are {Plan}, {Shop, Prep}, {Cook}, and {Serve}. Levels summarize precedence depth; they do not estimate duration or automatically produce an optimal real-world schedule.
Input rules, assumptions, and limits
Vertex labels are case-sensitive text. The optional vertex field accepts commas, semicolons, or line breaks. Edge endpoints are detected automatically, but an isolated vertex must be listed explicitly. Put one directed edge on each line using A -> B, A → B, or A,B; the first endpoint is the prerequisite and the second is the dependent.
Whitespace around a label is ignored while spaces inside it are retained. Labels cannot contain commas, semicolons, arrows, or line breaks. Repeated edges are ignored after the first and reported in the result. Self-loops are accepted as graph input but correctly reported as a one-vertex directed cycle.
The calculator supports up to 500 vertices, 20,000 nonempty edge lines, 50,000 distinct edges, and labels up to 80 characters. These limits prevent accidental extreme input from freezing the browser. Input-order tie-breaking follows the first occurrence in the vertex field and then the edge list. Natural ordering uses the browser's locale-aware numeric comparison.
Definitions follow the U.S. National Institute of Standards and Technology's topological order, topological sort, and directed acyclic graph entries. The indegree-removal method is Kahn's algorithm, introduced in A. B. Kahn's 1962 paper Topological sorting of large networks.
Calculation note: DAG sorting, tie handling, uniqueness, level calculation, duplicate edges, isolated vertices, self-loops, multi-vertex cycles, and export fields checked by the Starlight Tools editorial team. Last reviewed: .
Topological sort calculator FAQ
What is a topological sort?
It is a linear ordering of a directed acyclic graph in which every source of a directed edge appears before that edge's destination. It is commonly used to represent prerequisite or dependency order.
Can a graph have more than one topological order?
Yes. Whenever two or more vertices can validly be chosen next, different choices can produce different valid orders. The result states whether the graph's topological ordering is unique.
Why can a cyclic graph not be topologically sorted?
A directed cycle creates contradictory precedence. For example, A → B → C → A requires A before B, B before C, and C before A. No linear order satisfies all three edges.
How does Kahn's algorithm work?
It repeatedly selects a zero-indegree vertex, appends that vertex to the order, and removes its outgoing edges. If the process cannot select a vertex before every vertex has been processed, the remaining graph contains a cycle.
How are ties resolved?
Input order prefers whichever available vertex was first seen. Natural label order compares labels with numeric awareness, so item2 precedes item10. A tie-breaker selects one valid answer; it does not change whether an answer exists.
What do the calculated levels mean?
Sources are level 0. Every other vertex is assigned one more than the largest level among its prerequisites. Therefore every edge points to a higher level. Levels describe dependency depth, not elapsed time.
Does this calculator upload my graph?
No. The graph is parsed and sorted in your browser. Copying and CSV creation also happen locally, and this tool does not save entered vertices or edges.