topological sort

A topological sort, also called a topological ordering, is a linear arrangement of the vertices of a directed graph in which every vertex comes before all the vertices its edges point to. If the graph holds an edge from A to B, then A must appear somewhere before B in the ordering.

Such an ordering exists only when the graph is a directed acyclic graph (DAG), meaning its edges are directed and form no cycles. A cycle would require some vertex to come before itself, which no linear order allows. A DAG usually has many valid orderings rather than one, because two vertices with no path linking them may appear in either relative order.

Two standard algorithms produce a topological ordering, each visiting every vertex and edge once for a time complexity of O(V + E) for V vertices and E edges:

• Kahn’s algorithm repeatedly removes a vertex that has no incoming edges, adds it to the result, and deletes its outgoing edges, often using a queue to hold the vertices that currently qualify.
• Depth-first search visits each vertex through recursion, records it as the traversal unwinds, and then reverses that finishing order to produce the result.

The widget below runs Kahn’s algorithm one step at a time. Each highlighted vertex has an in-degree of 0, meaning no edges point to it, so removing it and deleting its outgoing edges is always safe, which often drops another vertex to in-degree 0 and makes it ready. When several vertices qualify at once, the choice among them is what makes the final order non-unique.

The ordering answers any question about sequencing work when some items depend on others. Build systems compile files in dependency order, package managers install prerequisites first, and spreadsheets recalculate a cell after the cells it references. Python provides topological sorting through the graphlib module and its TopologicalSorter class.

Related Resources

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

• Introduction to Sorting Algorithms in Python (Course)
• Build a Maze Solver in Python Using Graphs (Tutorial)
• Thinking Recursively in Python (Tutorial)
• Using Python's pip to Manage Your Projects' Dependencies (Tutorial)
• Dependency Management With Python Poetry (Tutorial)
• Sorting Algorithms in Python (Quiz)
• Mazes in Python: Build, Visualize, Store, and Solve (Course)
• Thinking Recursively With Python (Course)
• Thinking Recursively in Python (Quiz)
• A Beginner's Guide to pip (Course)
• Using Python's pip to Manage Your Projects' Dependencies (Quiz)
• Managing Dependencies With Python Poetry (Course)
• Dependency Management With Python Poetry (Quiz)