[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/topological_sort.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "topological sort" type: concept related: [Topological Sort, Depth First Search] source: https://www.jemoka.com/posts/kbhtopological_sort/ confidence: high status: active --- For directed acyclic graphs, a topological sort of a directed graph is such that if there’s an edge \(A \to B\), then \(A\) comes before \(B\) in the sort (i.e. there’s not an edge from \(B\) to \(A\)). Under direct acyclic graphs, a topological sort always exist. solving topological sort with depth first search In a DAG, you can always go from larger finish times to smaller finish times in depth first search to be able to get a topological sort. Case 1: \(B\) is a descendant of \(A\) in the DFS tree. Then \(B\) finish time would be earlier than \(A\) finish time. Then \(A\) would be sorted first. Case 2: \(A\) is a descendant of \(A\). Then, we must have explored \(B\) before \(A\) (otherwise if we explored \(A\) first we would have gotten to \(B\) and hence it would be children). And so \(B\) finish time is earlier than \(A\) finish chem. Case 3: neither is a descendant (its not connected): then one component will start and finish fully before another, this makes topo sort ordering not mater.