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.


  1. Create a List for save the order
  2. For each source in the DAG, repeat step 3-4
  3. Do a DFS (Recursion) with the root node is a source
  4. Push the node into a List when it is “finish”
  5. Reverse the order of List

Time Complexity
It has same time complexity with DFS, which is O (| V | + | E |)

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