# Python-powered perfection: Topological Sorting Algorithm.

## Topological sort use case.

In Computer Sciense a topological sort of a directed graph (Directed Acyclic Graph - DAG) is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The method applicable for graphs that have no directed cycles - directed acyclic graphs. Topological sort is a graph bypassing mode in which each node v is visited only after all its dependencies are visited.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.

The typical use case of topological sorting is a tasks scheduling based on their relations. The Python code can be implemented in recursive and non-recursive way, below recursive code is presented.

1. ## Topological sorting Algorithm Python code:

2. ``````
from collections import defaultdict

#Class for a graph
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices

# add an edge to graph
self.graph[u].append(v)

# A recursive function used by Main function
def TopologicalSortUtil(self,v,visited,stack):
visited[v] = True

for i in self.graph[v]:
if visited[i] == False:
self.TopologicalSortUtil(i,visited,stack)

stack.insert(0,v)

# Main function
def TopologicalSort(self):
visited = [False]*self.V
stack =[]

for i in range(self.V):
if visited[i] == False:
self.TopologicalSortUtil(i,visited,stack)

print (stack)

g = Graph(6)

print ("Topological Sort:")
g.TopologicalSort()
``````
3. ## Topological sorting Algorithm code output:

4. OUT: Topological Sort:
[1, 5, 3, 2, 0, 4]