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()

Output

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.