▶

Topological Sort Calculator

DAG · Kahn's Algorithm · DFS · Cycle Detection · All Orderings

Find a valid linear ordering of a directed acyclic graph (DAG). Supports Kahn's BFS algorithm and DFS approach. Detects cycles and enumerates all valid orderings for small graphs.

Quick Examples

Input Method:

Edge List (one per line or comma-separated, e.g. A→B or A-B)

Accepted formats: A→B A->B A-B A,B separated by commas or newlines.

Algorithm:

Nodes

—

Vertices

Edges

—

Directed edges

Is DAG?

—

Cycle check

Valid Orderings

—

For n ≤ 7 nodes

Step-by-Step Trace — Kahn's Algorithm

Each step: dequeue a node with in-degree 0, add to result, decrement neighbors' in-degrees.

Step	Dequeued	Queue After	In-Degrees (changed)	Result So Far

DFS Finish Times

Nodes sorted by decreasing DFS finish time give the topological order.

Node	Discover Time	Finish Time	Topological Position

What Is Topological Sort?

Topological sort (also called topological ordering) is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u appears before vertex v in the ordering. Unlike standard sorting, topological sort is about dependency order, not numerical or alphabetical comparison.

Topological sort only exists when the graph has no directed cycles. If a cycle exists — say A → B → C → A — there is no consistent ordering because A must precede B, B must precede C, and C must precede A, which is impossible simultaneously.

Directed Acyclic Graphs (DAGs)

A directed acyclic graph (DAG) is a graph in which every edge has a direction and there are no directed cycles. DAGs naturally arise whenever you model dependencies: task A must complete before task B can start. The edges represent "must come before" relationships.

Common examples include: course prerequisites (Calculus before Differential Equations), software build dependencies (compile library before linking executable), recipe steps (chop ingredients before cooking), and spreadsheet cell formulas (compute D1 = A1 + B1 before E1 = D1 * 2).

Kahn's Algorithm (BFS-based)

Kahn's algorithm, published by Arthur B. Kahn in 1962, is the most intuitive approach. It works by repeatedly removing nodes that have no dependencies:

Compute in-degree for each node (number of incoming edges).
Initialize queue with all nodes having in-degree 0 (no dependencies).
While queue is not empty: dequeue node u, append to result, and for each neighbor v of u, decrement in-degree[v]. If in-degree[v] becomes 0, enqueue v.
Cycle check: if result contains all nodes, the graph is a DAG. Otherwise, remaining nodes form a cycle.

Time complexity: O(V + E) where V is the number of vertices and E is the number of edges. This is optimal since every vertex and edge must be examined at least once.

DFS-based Topological Sort

The DFS-based approach uses depth-first search and records each node's finish time — the moment DFS fully explores all descendants. Nodes with higher finish times come earlier in the topological order. A cycle is detected when DFS encounters a back edge — an edge pointing to an ancestor in the current DFS path (a "gray" node in the three-color marking scheme).

Both Kahn's and DFS-based approaches have the same O(V + E) complexity, but they produce different valid orderings for the same graph (when multiple orderings exist).

Applications of Topological Sort

Domain	Application	DAG Meaning
Build Systems	GNU Make, Bazel, npm	Source file A must compile before linking B
Education	Course scheduling	Prerequisite course must be taken first
Spreadsheets	Formula recalculation	Cell must be computed before dependent cells
Compilers	Instruction scheduling	Instruction result needed by later instruction
Package Managers	Apt, pip, npm install	Dependency must install before dependents
Project Planning	Critical path method	Task must complete before successor can start

How Many Valid Orderings Exist?

A graph can have multiple valid topological orderings. For a chain A → B → C → D, there is exactly one valid ordering. But for a "diamond" A → B → D, A → C → D, both [A, B, C, D] and [A, C, B, D] are valid. The count of valid orderings depends on the graph structure and grows quickly — counting all orderings is a #P-complete problem. This calculator enumerates all orderings for small graphs (up to 7 nodes).

Cycle Detection Details

In Kahn's algorithm, a cycle is detected when the result contains fewer than V nodes after the queue empties. The remaining nodes are involved in cycles — each has at least one incoming edge from another cycled node, so no node in the cycle ever reaches in-degree 0. In DFS-based detection, encountering a "gray" node (currently being processed) during traversal signals a back edge and thus a cycle.

Frequently Asked Questions

What is topological sort?

Topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge u→v, vertex u appears before vertex v in the ordering. It is used to schedule tasks with dependencies, resolve build orders, and enforce course prerequisites.

What is a directed acyclic graph (DAG)?

A directed acyclic graph (DAG) is a directed graph with no directed cycles. You cannot start at any vertex and follow directed edges back to the same vertex. DAGs model dependency relationships, such as course prerequisites, build dependencies, and spreadsheet cell formulas.

How does Kahn's algorithm work?

Kahn's algorithm repeatedly removes nodes with no incoming edges. First compute in-degrees for all nodes. Add all zero-in-degree nodes to a queue. Each iteration: dequeue a node, add it to the result, and decrement in-degrees of its neighbors — enqueuing any that reach zero. If the result size equals the node count, you have a valid topological order. Otherwise a cycle exists.

Is topological sort unique?

No, topological sort is generally not unique. Multiple valid orderings can exist when nodes lack direct dependency relationships. For example, if only A→C and B→C exist, both [A, B, C] and [B, A, C] are valid. A unique ordering exists only when the graph forms a single chain (path graph).

What happens if a graph has a cycle?

If a directed graph has a cycle, topological sort is impossible. In Kahn's algorithm, the nodes forming the cycle never reach in-degree 0 and are never added to the result. The calculator detects this and identifies which nodes are involved in the cycle.

What is the time complexity of topological sort?

Both Kahn's algorithm and the DFS-based approach run in O(V + E) time — linear in the number of vertices and edges. This is optimal because every vertex and edge must be visited at least once to determine the ordering.

What are real-world applications of topological sort?

Topological sort powers build systems (GNU Make, npm, Bazel) for compilation order, course scheduling systems to enforce prerequisites, spreadsheet engines for formula recalculation order, package managers (pip, apt) for dependency install order, compiler instruction scheduling for optimization, and project management tools for task sequencing.