- Current
- Free or being visited
- Placed
- Cycle
Topological sort
Socks before shoes, foundations before walls, a course before the course that needs it. A topological sort puts the nodes of a graph with one-way edges in a row where every edge points forward. Pick Kahn's algorithm or the DFS method and step through to see the order grow, and add a cycle to see why no order is possible then. Press Play to watch the order grow, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Every edge is one-way, as its arrow shows: think of it as "this comes before that". Pick the method: Kahn's algorithm places nodes with no incoming edges first, and the number on each node is how many incoming edges it still has; the DFS method places each node in front once everything after it is placed. The row under the graph is the order so far. Tick Add a cycle to see how each method finds one. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Pick Kahn's algorithm or the DFS method.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch the order grow under the graph. Tick Add a cycle to see how each method finds one.
Kahn's algorithm
Count, for every node, how many edges point to it. A node with none depends on nothing, so it can go first. Place such a node, and remove its outgoing edges: the nodes they pointed to now have one incoming edge fewer, and some may reach zero and become free. Keep placing free nodes until none is left. If some nodes were never freed, they wait for each other in a cycle, and no topological order exists.
The DFS method
Run a depth-first search from each unvisited node. A node is finished when everything reachable from it has been finished, so everything that must come after it is already placed. Put each finished node at the front of the order, and the order comes out right. If the search follows an edge to a node it is still inside, that edge closes a cycle, and again no order exists.
Frequently asked questions
What is a topological sort?
An ordering of the nodes of a directed graph in which every edge goes from an earlier node to a later one. If the edges mean "must come before", it is an order in which all the tasks can be done.
When does a topological order exist?
Exactly when the graph has no directed cycle: it is a directed acyclic graph, or DAG. With a cycle, every node on it would have to come before itself.
Is the topological order unique?
Usually not. Whenever two nodes are not connected by a chain of edges, either can go first, so a graph can have many valid orders. Kahn's algorithm and the DFS method often give different ones.
How fast is a topological sort?
Both methods look at every node and every edge a fixed number of times, so the work grows with the number of nodes plus the number of edges.
Is my graph sent anywhere?
No. The graph is made and sorted in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor