|
Topological Sort is using to find out the topological ordering of a DAG (Directed acyclic graph - A Directed graph with not directed cycles). For every edge form x to y, x is before y in thetopological order. DAG must exists sources and sinks. Source is node that doesn’t contain incoming edge and sink is a node that doesn’t contains outgoing edge. There could be multiple sources and sinks in a DAG.
In a DFS, it has “start” and “finish” time for a node. Start is the time of First time Discovery the node and Finish is the Final departure of that node. As you can see, the topological order is the reverse of the order of finish time of each node. DFS will travel the graph until the most depth as it can.
Application sample:
Production Line in an industry: A product build up by different components, and a component is usually base on other smaller components. Source will be the raw material and sink will be the product. Topological sort can find out the order of the production procedure in an industry.
Algorithm
- Create a List for save the order
- For each source in the DAG, repeat step 3-4
- Do a DFS (Recursion) with the root node is a source
- Push the node into a List when it is “finish”
- Reverse the order of List
|
Time Complexity
It has same time complexity with DFS, which is O (| V | + | E |)
SpaceComplexity
It need the space of DFS with the space of list store the finish time of all nodes, so the space complexity is O (| V |)
Pseudo Code
Create a list as Topological_order
Topological_Sort (Graph)
For each Node n in Graph do
If Incoming degree of n is 0 then
DFS (Graph, n)
Return the reverse of Topological_order
DFS (Graph, Node)
Mark Node as visited
For each neighbors n of Node do
If n is not visited then
Mark n as visited
DFS (Graph, n);
Push Node into Topological_order |
|