[Verse 1] Directed graph with arrows pointing clean Dependencies flowing like a data stream Before you process node B you need node A Topological ordering shows the way Khan's algorithm starts with zero inbound Queue up vertices where no arrows are found Remove each node and cut its connections Decrement counts in systematic directions [Chorus] Sort it topological, dependencies logical Zero in-degree, add to the queue methodically Process and remove, update the count Acyclic structure is paramount Topo-sort, linear arrangement Prerequisites in perfect arrangement [Verse 2] DFS approach goes deeper in the maze Post-order traversal through recursive plays Stack the finished vertices as you retreat Reverse that order and your sort's complete Course scheduling needs this algorithmic dance Software builds require dependency advance No circular references or infinite loops Directed acyclic graphs keep you in groups [Chorus] Sort it topological, dependencies logical Zero in-degree, add to the queue methodically Process and remove, update the count Acyclic structure is paramount Topo-sort, linear arrangement Prerequisites in perfect arrangement [Bridge] If cycles exist the sort will fail Remaining vertices tell the tale Partial ordering becomes total line Time complexity stays linear fine O of V plus E for the running cost When dependencies matter most [Outro] From source to sink the order flows Topological wisdom grows Dependencies resolved with algorithmic grace Every vertex finds its place
← A* search | Tarjan's algorithm (strongly connected components) →