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.
0 2 1 3
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
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()