Topological Sorting

A topological sorting of a directed graph G is a linear ordering of its vertices such that for every directed edge u->v, u comes before v in the ordering. A topological sorting is possible if and only if the graph has no directed cycles i.e., it is a Directed Acyclic Graph (DAG). It is always possible to find a topological order for a DAG and this can be done in linear time.

Topological sorting of a DAG can be found with DFS. During the depth-first traversal of the graph, just when a vertex finishes expanding (i.e., all its outlinks have been visited), add it to a stack. The order of vertices in the stack represents the topological order of the DAG.

Pseudocode for topological sorting :

Thus, the time complexity of finding topological sorting is same as that of DFS i.e., O(V + E).

Take a look at C++ implementation.

Try your hand at problems TOPOSORT and RPLA, which use this idea.

Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

4 thoughts on “Topological Sorting

  1. Hello sir,Have you done toposort on spoj using this implementation only ?I mean in that question it is required to print lexiographically smallest toposort.Have you done something with your code to get Ac in that question or just used this code only.As far as I know there can be many toposort for a DAG.So my question is that how to get Lexiographically smallest ?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s