How to implement Topological Sorting in Python

This Python tutorial helps you to understand what is topological sorting and how Python implements this algorithm. First, we will learn what is topological sorting.

Topological sorting in Python

Definition :

Topological Sorting is an ordering of vertices in such a way that for every directed edge ab, node or vertex a should visit before node “b” or vertex “b”.

Example:-

Consider a graph,

1 -> 2 -> 3

The topological ordering or sorting of the graph is 1, 2, 3. That means in order to visit vertex 3, vertex 2 should be visited first. In order to visit vertex 2, vertex 1 must be visited.

There are two conditions in order to find a topological ordering or sorting of a graph. Those are:-

  • The graph should be directed acyclic graph
  • The vertex in a topological graph should be a vertex with no incoming edges.

Algorithm for Topological Sorting

  • Step -1:- Identify vertices that have no incoming edges. Select that vertex as starting vertex of a graph
  • Step -2:- Delete the starting vertex or the vertex with no incoming edges and delete all its outgoing edges from the graph. Place the deleted vertex in the output list.
  • Step -3:- Repeat Step -1 and Step -2 until the graph is empty.

Implementation of Topological Sorting in Python

Source Code :

from collections import defaultdict


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

    def addEdge(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 topoSortvisit(self, s, visited, sortlist):
        visited[s] = True

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

        sortlist.insert(0, s)

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

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

        print(sortlist)


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

    g.addEdge(1, 2)
    g.addEdge(1, 3)
    g.addEdge(2, 4)
    g.addEdge(2, 5)
    g.addEdge(3, 4)
    g.addEdge(3, 6)
    g.addEdge(4, 6)
  
    print("Topological Sort:")
    g.topoSort()

Output:-

Topological Sort:

[1, 3, 2, 5, 4, 6]
Explanation:-
  • Vertex 1 has no incoming edges so it becomes the starting node.
  • Vertex 1 has two outgoing edges, vertex 2 and 3.
  • The ordering can start with either 1, 2 or 1, 3.
  • There is no cyclic component in the above graph.

You can also read,

Leave a Reply