Understanding the topological sort algorithm

The topological sort algorithm sorts the nodes of a graph in a topological order. For the algorithm to work, the graph should be a directed acyclic graph, as no topological order exists for a cyclic graph. Moreover, there can be many topological orders for a directed acyclic graph, and all of them can be correct. In this lesson, we will learn about the depth-first search-based algorithm used to find a topological order.

A directed acyclic graph can have multiple correct topological orderings.

Algorithm

The topological sort algorithm is really simple to understand as it is only a series of depth-first searches. Every depth-first search discovers a section of the topological order of the entire graph. These individual sections are stitched together to get the topological order of the whole graph. We will learn more about the proof of correctness of the algorithm later in the lesson.

This topological sort algorithm only works for directed acyclic graphs and returns a topological order of nodes. There can be many correct topological orders for a graph and this algorithm only returns one of those.

Consider we have the following graph, and we need to find the topological order of nodes for it.

Find a topological order of nodes for the graph.