Topological Sorting

In graph theory, a topological sorting of a directed graph is a linear ordering of vertices of graph such that if there is a directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Note: Graph must be directed and acyclic.

Example Input

Expected Output

0 2 1 3

Pseudocode

solution(v,Check_Visited,sortGraph):

v <- visited

for i in Graph[v]

if i is not visited

// recursive call

solution(i,Check_Visited,sortGraph)

insert v at first index of sortGraph

topologicalSort():

sortGraph =[]

for i in  range(V):

if i is not visited

// call

solution(i,Check_Visited,sortGraph)

sortGraph <- print

Implementation in Python

from collections import defaultdict

Graph = defaultdict(list)

V = 0

def  addEdge(u,v):

Graph[u].append(v)

def  solution(v,Check_Visited,sortGraph):

Check_Visited[v] = True

for i in Graph[v]:

if Check_Visited[i] == False:

solution(i,Check_Visited,sortGraph)

sortGraph.insert(0,v)

def  topologicalSort():

Check_Visited = [False]*V

sortGraph =[]

for i in  range(V):

if Check_Visited[i] == False:

solution(i,Check_Visited,sortGraph)

print(*sortGraph)

V = 4

addEdge(0, 1);

addEdge(0, 2);

addEdge(0, 3);

addEdge(1, 3);

addEdge(2, 3);

addEdge(2, 1);

topologicalSort()