Topological sort of an acyclic directed graph

Topological sorting forms with the ordering of all its vertices topologically. A topological ordering of any edge “U–>V” in an acyclic directed graph starts with “U” then “V”. For example we can think of any processes dependency in which task ‘U’ needs to finish first to execute process ‘V’.

We cannot do topological sorting on cyclic graphs as cyclic graphs leads to an infinite ordering cycle.

To better understand this algorithm let’s consider below acyclic directed graph.

Acyclic directed graph with 6 nodes.

There may be multiple answers for topological sort of an acyclic directed graph, one of which is { 3, -9, 8, 5, -3, 4 } If we calculate using DFS.

Here we store the Depth-first traversed elements in a stack, which finally contains all elements in topologically sorted order. Let’s see the code for this algorithm.

void tsUtil(Vertex *v, stack<Vertex> &st)
{
    v->visited = true;
    list<Vertex *>::iterator itr;
    for (itr = v->edges.begin(); itr != v->edges.end(); itr++)
    {
        Vertex *tmp = *itr;
        if (!tmp->visited)
        {
            tsUtil(tmp, st);
        }
    }
    st.push(*v);
}
void topologicalSort()
{
    stack<Vertex> result;
    list<Vertex *>::iterator itr;
    for (itr = vertices.begin(); itr != vertices.end(); itr++)
    {
        Vertex *ver = *itr;
        if (!ver->visited)
        {
            tsUtil(ver, result);
        }
    }
    while (!result.empty())
    {
        cout << result.top().data << " ";
        result.pop();
    }
    cout << endl;
}

Complexity of this algorithm is O(E*V). We have a lot of real-world applications that use this topological sort. For example process dependencies, code compilation dependencies, and linker dependencies.

Let’s see the complete code for this algorithm in following gist.

// Output
3 -9 8 5 -3 4

This is all about the topological sort of an acyclic directed graph. If you know any better solution to solve this problem, please let our readers know by commenting here below. Happy Learning!.