The Graph Theory | Topological Sort

Within the last blog post we understood the algorithm related to depth-first search. Within this section we use depth first search to perform topological sort of a directed acyclic graph (DAG). Within this blog post we will discuss the following topics

• Introduction to topological sort
• Understand topological sort via example
• Write pseudocode for the same
• Analyze the complexity of topological sort

Introduction to topological sort

A topological sort of a directed acyclic graph (DAG) G=(V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. Topological sort is different from usual kind of sorting studied in previous blog post.

Basically, what it means by u appears before v in the ordering is if we are inserting ‘u’ node into the stack, then until node ‘v’ is pushed into stack we won’t pop out node ‘u’ from the stack.

Let us explain it via example and write a pseudocode for the same.

Let us write a pseudocode for the same.

The above algorithm is simple, we just modified our DFS algorithm to follow topological sort. First, we color all the nodes as white and change to ancestor as nil and time as 0 since no node has been parsed. Then we cover all the adjacent vertex of current node using TOPOLOGICAL-VISIT and recursively call this function and once it reaches the base case i.e when no adjacent element is white we come out of the loop and color is black and insert the element into the stack.

Since we are recursively calling the function, it means that the adjacent element of the adjacent element of the source element will be parsed first and hence it goes deeper into the graph.

Then finally we print the stack to get our desired output sequence.

Analyzing the complexity of topological sort

We can perform topological sort in θ (V+E) time, since depth-first search takes θ (V+E) time and it takes O(1) time to insert each of the |V| vertices into the array.

That’s all folks! We have covered topological sort in this blog post. We understood what topological sort is, explained it via example, wrote a pseudocode for the same and analyzed its complexity. Within our next blog post we are going to look at other graph algorithms like Bellman-Ford algorithm and Dijkstra’s algorithm.