7.3 Topological Ordering

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```
 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk