 # 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 vu comes before v in the ordering.

Note: Graph must be directed and acyclic.

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() ```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.