Topological Sort Algorithm

inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image

Creating our “Directed Graph”

class Graph:
    def __init__(self, Nodes, is_directed = False):
        self.nodes = Nodes
        self.adj_list = {}
        self.is_directed = is_directed
        for node in self.nodes:
            self.adj_list[node] = []
    def add_edge(self, u, v):
        if not self.is_directed:
    def degree(self,node):
        '''Total number of edges coming out a given node'''
        deg = len(self.adj_list[node])
        return deg
    def print_adj_list(self):
        for node in self.nodes:
            print(node, "->", self.adj_list[node])
    def __len__(self):
        return len(self.nodes)
    def __getitem__(self, node):
        """retrives items from out Node/vertex"""

        return  self.adj_list[node]
    def __iter__(self):
        """ This will allow us to iterate over our Graph Object"""
        """ We can iterate over the keys or "Vertexs" by: """
        """ using just the Object->  graph:  """
        return iter(self.adj_list)

Lets add out Edges and Nodes

all_edges = [

nodes = ["A","B","C","D","E","F","G","H","I","J","K","L","M"]

Lets create a Graph Object

graph1 = Graph(nodes, is_directed = True)

for u,v in all_edges:


Output of Graph:

A -> ['D']
B -> ['D']
C -> ['B', 'A']
D -> ['H', 'G']
E -> ['A', 'D', 'F']
F -> ['K', 'J']
G -> ['I']
H -> ['J', 'I']
I -> ['L']
J -> ['M', 'L']
K -> ['J']
L -> []
M -> []

Let’s add a Deque Data Structure

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):

    def addRear(self, item):
        """ add to rear"""

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)
    def _print(self):
        '''print Deque Values'''
        return self.items

Now lets Create a Topological Function and Corresponding DFS

def dfs(graph, source, stack, visited):

    for neighbour in graph[source]:
        if neighbour not in visited:
            dfs(graph, neighbour, stack, visited)


def topological_sort_of(graph):
    stack = Deque() 
    visited = []

    for vertex in graph:
        if vertex not in visited:
            dfs(graph, vertex, stack, visited)
    return stack

Running our Topological Sort Algorithm

topological_ordering = topological_sort_of(graph1)


Topological Ordering Output:

['E', 'F', 'K', 'C', 'B', 'A', 'D', 'G', 'H', 'I', 'J', 'L', 'M']