Select Page

# Python program for Topological Sorting using Python

by | Jun 29, 2021 | Python Programs

Home » Python » Python Programs » Python program for Topological Sorting using Python

## Introduction

For topological sorting of graph the graph needs to be DAG (Directed Acyclic Graph).The topological sorting of DAG is the ordering of the vertices for edge uv, such that vertex u is placed before v in ordering.

## Program

```from collections import defaultdict

class Graph:
def __init__(self,v):
self.graph = defaultdict(list)
self.V = v

def append(self,u,v):
self.graph[u].append(v)

def sort_util(self,v,visited,ele_stack):
visited[v] = True
for ele in self.graph[v]:
if visited[ele] == False:
self.sort_util(ele,visited,ele_stack)
ele_stack.insert(0,v)

def topological_sort(self):
visited = [False]*self.V
ele_stack =[]
for ele in range(self.V):
if visited[ele] == False:
self.sort_util(ele,visited,ele_stack)
print(ele_stack)
g = Graph(4)
g.append(4,1);
g.append(4,2);
g.append(3,2);
g.append(4,3);
g.append(1,3);
print("The Topological Sort is:  ")
g.topological_sort()```

## Explanation

In the above code, we have followed below steps:

• Create an adjacency list containing the vertices and their associated node vertices.
• Create one list visited, with the vertices and there visited value as false.
• Now, we will focus on topological sorting. Visit the vertex(i) and mark is true in visited list and recur all its adjacent vertex. Append the current vertex to the result stack.
• Follow the above step for the vertex elements and return the stack from top to bottom.

## Author

• A Full Stack Developer with 10+ years of experience in technical content creation.

• 