Topological Sort

Besides, traversing and searching shortest path in a graph, you can sort vertices in directed acyclic graph. This type of sorting is called topological sort and it can be useful in task scheduling application. The tasks can have dependencies on other tasks. These dependencies can be simple, then we can arrange the tasks in a linked list and execute task one by one. In case if we have more that one dependency, then we will use DAG, to represent these tasks.

gag_toposort

The topological sorting can be applied only on DAG, because cycle doesn’t give a chance to prioritize tasks.

Now it’s time to consider an example from real life and today we are going to make an iced coffee. The recipe is quite simple, we need coffee, sugar, water and whipped cream. On the diagram below I have illustrated all steps to make iced coffee.

iced_coffee

Basing on this diagram you might already figure out the precise order of steps. This order is same as it would be produced by the topological sort.

toposort_output

 

Thus, the topological sort is a linear ordering of vertices such that if the graph G contains an edge (v,w) then the vertex v comes before the vertex w in the ordering.

Implementation

There are two very common implementations of the topological sort. One of the first topological sorting algorithms is known as Khan algorithm. It was proposed by Arthur Kahn in 1962.

Another approach is based on depth-first search algorithm. The idea of the algorithm is simple, you start DFS and calculate finishing time. When finish time for vertex is calculated you need to add this vertex into the front of the array list.

Here is my version of DFS based and Kahn topological sort on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/TopologicalSort.java.

Leave a Reply