Topological Sort Examples

Graph Theory · Axiom Academy

EXAMPLE Topological Sort Examples Master topological sorting through practical examples Example 1: Course Prerequisites A student must take courses in an order that respects prerequisites. Find a valid ordering. Source files must be compiled in order based on dependencies. Find compilation order. Excellent work! You've mastered topological sorting. Here's what we learned: DAG Requirement: Topological sort only works on Directed Acyclic Graphs (DAGs). If there's a cycle, no valid ordering exists because tasks would have circular dependencies. Kahn's Algorithm: Start with nodes having in-degree 0 (no dependencies), process them, and reduce in-degrees of their neighbors. Repeat until all nodes are processed. Multiple Valid Orderings: When multiple nodes have in-degree 0 simultaneously, we can process them in any order, leading to different but equally valid topological orderings. Real-World Applications: Used in course scheduling, build systems (make, gradle), task scheduling, package managers, and resolving symbol dependencies in linkers. Complexity: Kahn's algorithm runs in O(V + E) time, where V is the number of vertices and E is the number of edges, making it very efficient. Cycle Detection: If the algorithm finishes but hasn't processed all vertices, the graph contains a cycle and cannot be topologically sorted. Topological sorting is a fundamental algorithm for dependency resolution in computer science!

This is the written version of the interactive lesson above. See the full Graph Theory course.