Algorithms
Topics:
Topological Sort
• Searching
• Sorting
• Greedy Algorithms
• Graphs
• String Algorithms
• Dynamic Programming

# 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:

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
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:

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

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$.

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$.

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

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 = []

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.

Contributed by: Vaibhav Jaimini
Уведомления

?