Algorithms
Topics:
Topological Sort

Topological Sort

Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices $$v_1, v_2, ... v_n$$ in such a way, that if there is an edge directed towards vertex $$v_j$$ from vertex $$v_i$$, then $$v_i$$ comes before $$v_j$$. For example consider the graph given below:

enter image description here

A topological sorting of this graph is: $$1$$ $$2$$ $$3$$ $$4$$ $$5$$
There are multiple topological sorting possible for a graph. For the graph given above one another topological sorting is: $$1$$ $$2$$ $$3$$ $$5$$ $$4$$
In order to have a topological sorting the graph must not contain any cycles. In order to prove it, let's assume there is a cycle made of the vertices $$v_1, v_2, v_3 ... v_n$$. That means there is a directed edge between $$v_i$$ and $$v_{i+1}$$ $$(1 \le i \lt n)$$ and between $$v_n$$ and $$v_1$$. So now, if we do topological sorting then $$v_n$$ must come before $$v_1$$ because of the directed edge from $$v_n$$ to $$v_1$$. Clearly, $$v_{i+1}$$ will come after $$v_i$$, because of the directed from $$v_i$$ to $$v_{i+1}$$, that means $$v_1$$ must come before $$v_n$$. Well, clearly we've reached a contradiction, here. So topological sorting can be achieved for only directed and acyclic graphs.

Le'ts see how we can find a topological sorting in a graph. So basically we want to find a permutation of the vertices in which for every vertex $$v_i$$, all the vertices $$v_j$$ having edges coming out and directed towards $$v_i$$ comes before $$v_i$$. We'll maintain an array $$T$$ that will denote our topological sorting. So, let's say for a graph having $$N$$ vertices, we have an array $$in\_degree[]$$ of size $$N$$ whose $$i^{th}$$ element tells the number of vertices which are not already inserted in $$T$$ and there is an edge from them incident on vertex numbered $$i$$. We'll append vertices $$v_i$$ to the array $$T$$, and when we do that we'll decrease the value of $$in\_degree[v_j]$$ by $$1$$ for every edge from $$v_i$$ to $$v_j$$. Doing this will mean that we have inserted one vertex having edge directed towards $$v_j$$. So at any point we can insert only those vertices for which the value of $$in\_degree[]$$ is $$0$$.
The algorithm using a BFS traversal is given below:

topological_sort(N, adj[N][N])
        T = []
        visited = []
        in_degree = []
        for i = 0 to N
                in_degree[i] = visited[i] = 0

        for i = 0 to N
                for j = 0 to N
                        if adj[i][j] is TRUE
                                in_degree[j] = in_degree[j] + 1

        for i = 0 to N
                if in_degree[i] is 0
                        enqueue(Queue, i)
                        visited[i] = TRUE

        while Queue is not Empty
                vertex = get_front(Queue)
                dequeue(Queue)
                T.append(vertex)
                for j = 0 to N
                        if adj[vertex][j] is TRUE and visited[j] is FALSE
                                in_degree[j] = in_degree[j] - 1
                                if in_degree[j] is 0
                                        enqueue(Queue, j)
                                        visited[j] = TRUE
        return T
Let's take a graph and see the algorithm in action. Consider the graph given below:
enter image description here

Initially $$in\_degree[0] = 0$$ and $$T$$ is empty

enter image description here

So, we delete $$0$$ from $$Queue$$ and append it to $$T$$. The vertices directly connected to $$0$$ are $$1$$ and $$2$$ so we decrease their $$in\_degree[]$$ by $$1$$. So, now $$in\_degree[ 1 ] = 0$$ and so $$1$$ is pushed in $$Queue$$.

enter image description here

Next we delete $$1$$ from $$Queue$$ and append it to $$T$$. Doing this we decrease $$in\_degree[ 2 ]$$ by $$1$$, and now it becomes $$0$$ and $$2$$ is pushed into $$Queue$$.

enter image description here

So, we continue doing like this, and further iterations looks like as follows:

enter image description here

So at last we get our Topological sorting in $$T$$ i.e. : $$0$$, $$1$$, $$2$$, $$3$$, $$4$$, $$5$$

Solution using a DFS traversal, unlike the one using BFS, does not need any special $$in\_degree[]$$ array. Following is the pseudo code of the DFS solution:

T = []
visited = []

topological_sort( cur_vert, N, adj[][] ){
    visited[cur_vert] = true
    for i = 0 to N
        if adj[cur_vert][i] is true and visited[i] is false
        topological_sort(i)
    T.insert_in_beginning(cur_vert)
}

The following image of shows the state of stack and of array $$T$$ in the above code for the same graph shown above.

enter image description here

Contributed by: Vaibhav Jaimini
Notifications
View All Notifications