Topological Sort Demo

Overview

The Topological Sort Demo shows how to linearly order vertices in a directed acyclic graph (DAG) such that for every directed edge (u,v), vertex u comes before v in the ordering. Create dependency graphs and watch as the algorithm finds a valid topological ordering. Perfect for understanding task scheduling, build systems, course prerequisites, and any scenario involving dependencies.

Open in new tab

Tips

• Topological sort only works on directed acyclic graphs (DAGs)
• If the graph has a cycle, no valid topological ordering exists
• Multiple valid orderings may exist for the same graph
• Uses DFS-based algorithm: finish times determine the ordering
• The algorithm detects cycles and reports if topological sort is impossible
• Applications: task scheduling, makefile dependencies, course prerequisites
• Nodes are numbered in reverse order of DFS finish times
• Try adding edges that create cycles to see cycle detection in action