Python Program for Topological Sorting

DFS has been modified to create a topological sort. In this tutorial, we will perform topological sorting on a graph using python language.

Topological Sort - A basic Introduction

Topological sorting is the ordering of vertices in such a way that node or vertex a should visit before node or vertex b for every directed edge ab. Executing DFS traversal starting at some node in the graph and finishing with DFS on one of the unvisited nodes if there are any remaining This is repeated until no nodes remain unvisited. The topological ordering of the DAG is then determined by sorting the completed times corresponding to each node in decreasing order.

Let us look at the below diagram:

The topological ordering or sorting of the graph is A, B, C, D, E, F. That means to visit vertex B, vertex A should be visited first. To visit vertex C, vertex A, B must be visited, and so on.

The following two conditions will be used for sorting an array using the topological method:

• The graph should be acyclic and directed.
• In a topological graph, the vertex should be a vertex with no incoming edges.

Algorithm

As of now, we have a rough understanding of how topological sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Import defaultdict
2. Create a class graph
3. Create a function edge()
4. Create a function visit()
5. create a function topological_sort()
6. Identify vertices that have no incoming edges.
7. Select that vertex as starting vertex of a graph
8. Delete the starting vertex or the vertex with no incoming edges and delete all its outgoing edges from the graph.
9. Place the deleted vertex in the output list.
10. Repeat until the graph is empty
11. The graph is now sorted.
12. Print the result

Program for Shell Sort

As discussed above in the algorithm, let us now dive into the programming part of the topological sort operation influenced by the algorithm.

from collections import defaultdict
class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def Edge(self, frm, to):
        self.graph[frm].append(to)

        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visit(self, s, visited, sortlist):
        visited[s] = True

        for i in self.graph[s]:
            if not visited[i]:
                self.visit(i, visited, sortlist)

        sortlist.insert(0, s)

    def topological_Sort(self):
        visited = {i: False for i in self.graph}

        sortlist = []
       
        for v in self.graph:
            if not visited[v]:
                self.visit(v, visited, sortlist)

        print(sortlist)

#driver code
if __name__ == '__main__':
 
    g = Graph(directed=True)

    g.Edge(1, 2)
    g.Edge(2, 3)
    g.Edge(3, 4)
    g.Edge(4, 5)
    g.Edge(5, 6)
    g.Edge(6, 7)
    g.Edge(7, 8)
    
    print("The Result after Topological Sort:")
    g.topological_Sort()

The result after Topological Sort:
[1, 2, 3, 4, 5, 6, 7, 8]

Conclusion

In this tutorial, we have performed a topological sort operation in python to sort a graph. The topological sort algorithm doesn't have stability. The time complexity of the topological sort algorithm is O(n+k) and the space complexity is O(max). We can use radic