Topological Sort
Visualize Kahn's algorithm and DFS for finding linear orderings of directed acyclic graphs.
Free theory articleVisualize Kahn's algorithm and DFS for finding linear orderings of directed acyclic graphs.
Concept & interpretation
Topological sort is a fundamental algorithm for directed acyclic graphs (DAGs). It produces a linear ordering of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This operation is impossible if the graph contains any cycles. It is widely used for scheduling tasks with dependencies, where one task must be completed before another can begin.