Summary: In this tutorial, we will learn what Topological Sort Algorithm is and how to sort vertices of the given graph using topological sorting.

Introduction to Topological Sort

A topological ordering is an ordering of the vertices in a directed graph where for each directed edge from vertex A to vertex B, vertex A appears before vertex B in the ordering.

Topological sort example

Topological sorting sorts vertices in such a way that every directed edge of the graph has the same direction.

Topological ordering is only possible for the Directed Acyclic Graphs (i.e., DAG). Graph with cycles cannot be topologically sorted.

It is important to note that the same graph may have different topological orders.

Algorithm for Topological Sort

We can sort the vertices of the graph in topological order using the depth-first search algorithm, because in topological ordering, the vertices without any child or neighbor vertex (leaf nodes in case of a tree) comes to the right or at last.

Using DFS, we traverse the graph and add the vertices to the list during its traceback process.

Since the traceback happens from the leaf nodes up to the root, the vertices gets appended to the list in the topological order.

We attach the visited vertices to the front of the list to ensure that the last visited vertices come to the right.

Here is the implementation of the algorithm in Python, C++ and Java:

Python

C++

Java

Output:

[A, C, B, E, F, D]

In the above programs, we have represented the graph using the adjacency list.

We are appending the vertices (which have been visited) in front of the order list so that the vertices in the list are in the same order as they were visited (i.e., the last visited vertex will come to a final).

The time complexity of the algorithm used is O(V+E) because DFS has to visit all the edges of the graph to create a topological order containing all vertices of the graph.

Application of Topological Sort

Topological sorting is useful in cases where there is a dependency between given jobs or tasks.

For example, if Job B has a dependency on job A then job A should be completed before job B.

For multiple such cases, we treat jobs as entities and sort them using topological sort to get their correct to do order.

Related Topics:

  1. Kahn’s Algorithm for Topological Sort

Leave a Reply