A topological sort of a directed acyclic graph (in short DAG) is a linear ordering of vertices such that if DAG contains a directed edge (u,v), then u appears always before v in the ordering. For example in below directed acyclic graph one of possible topological order is c a d b. Topological sort is not possible if a directed graph contains a cycle. if a directed graph contains a cycle then it is impossible to preserve the property of topological ordering.

Topological Sorting

Some real word applications which uses topological sorting.

Ubuntu Linux/OS package manager ( synaptic, apt-get).

It uses topological sorting to obtain the best possible order in which a set of Debian packages can be installed/removed.

 Maven Build system

Maven is a popular open source build tool for enterprise Java project.

Note: Topological sorting is used to solve classing scheduling and maximum flow problem in computer science.

Now let us an algorithm known as Kahn’s algorithm for topological sorting.

Kahn’s algorithm

  1. Determine the in-degree of each vertex of directed acyclic graph.
  2. Find the zero in-degree node and print it. After printing remove the vertex and all its outgoing edges from the graph. if there is no zero in-degree vertex in graph,the graph is cyclic and no topological sort possible.
  3. Continue to step 1 (recalculate the in-degree of remaining vertices of the DAG) and step 2, until the graph becomes empty.

Let us see below example graph and apply above algorithm on it. The below figure shows adjacency matrix and adjacency list representation of graph, on its left side.

Topological SortingIf we represent the graph nodes a as 0 , b as 1, c as 2 and d as 3 . The one of topological order  would be 0 2 3 1. Let us see the below implementation for topological order of above graph. To remove the 0 in-degree node (u) from the graph, we decrease the in-degree of each connected vertex from (u) by 1.

Ref: http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module4/basic_graph_algorithms.xhtml

Related Contents to follow