[Verse 1] Got a directed graph, no cycles in sight DAG is the foundation, gotta get it right Nodes represent tasks, edges show the flow Can't start the next one till the first one's done, you know Kahn's algorithm stepping to the plate Count incoming edges, calculate the weight Zero in-degree means you're ready to go Queue them up first, let the process flow [Chorus] Topo sort, topo sort, ordering the chain Remove the node, update the count, do it again DAG life, no cycles, dependencies clear Queue or stack, DFS track, algorithm's here Topo sort, topo sort, linear arrangement Prerequisite flow, that's the engagement [Verse 2] DFS approach coming from the back Recursive descent on the vertex stack Visit all the children, go deep in the tree Post-order collection, that's the key you see Finish time stamping, highest number first Reverse that order, quench your sorting thirst Both methods valid, different paths to take Same result guaranteed for the graph you make [Chorus] Topo sort, topo sort, ordering the chain Remove the node, update the count, do it again DAG life, no cycles, dependencies clear Queue or stack, DFS track, algorithm's here Topo sort, topo sort, linear arrangement Prerequisite flow, that's the engagement [Bridge] Course scheduling, task management too Build systems need it, compilation's due Deadlock detection, social networks flow Any time dependencies, topo's the way to go Linear time complexity, O of V plus E Efficient and elegant, that's the guarantee [Verse 3] Check for cycles first, before you begin Topological order only works within A DAG structure, acyclic and clean If there's a cycle, no linear scene Multiple solutions might exist in space Any valid ordering, you can embrace But the dependencies, they must be preserved Parent before child, that rule's observed [Chorus] Topo sort, topo sort, ordering the chain Remove the node, update the count, do it again DAG life, no cycles, dependencies clear Queue or stack, DFS track, algorithm's here Topo sort, topo sort, linear arrangement Prerequisite flow, that's the engagement [Outro] Dependencies sorted, algorithm complete West coast style, can't accept defeat Topological mastery, that's how we roll Graph theory knowledge, feeding your soul
← A* search | Tarjan's algorithm (strongly connected components) →