So, if you do a DFS and include a node in topological sort resultset only after all the nodes in its subtree(s) have been visited then You can extrapolate this concept and say all the nodes in a subtree is dependent on the root of that subtree.Īnd this is true for all subtrees and all nodes which has one or more subtrees. So u must beĮxecuted before v, which means in topological sort resultset u must come before v. So we would need to reverse the order to get the topological sort.Ī bit more explanation: We can view a graph as a dependency graph where an edge (u -> v) represent v is dependent on U. Reverse order of that of what a topological ordering should be. This way we will get all the vertices in totally Search path, until all the vertices in the graph are visited. While doing a DFS we will search for the sink vertices, and as we get a sink vertex we willĭisconnect that vertex from the graph and will then backtrack and search for the next sink vertex along the Put in a different way, one of the ways to prove that a graph is a DAG is to show that it has a topological ordering.Ĭorollary: A directed graph with no sink vertex must have cycle. So the graph needs to be a DAG (Directed Acyclic Graph). There is a very clear necessary condition for a directed graph to have a topological sorting, and that is it better be acyclic. When Does A Directed Graph Have A Topological Ordering ? Topological sorting can give you the sequence in which different courses can be taken by students so that they can complete the pre-requisite courses before taking a course. The prerequisite course(s) needs to be completed before taking the course. Topological sort can sequence tasks while respecting all sequence constraints without any conflict.Ī real world scenario: In most academic programs there are prerequisite courses for taking a specific course. Topological Sort is useful in scheduling tasks where precedence ordering matters, i.e, one task needs to be done before starting another. Every DAG has at least one Topological Ordering.
0 kommentar(er)
