iframe-proxy | Sunbelt Computer Software

36 lines (30 loc) · 819 Bytes

def topologicalSort(graph):

"""

Kahn's Algorithm is used to find Topological ordering of Directed Acyclic Graph

using BFS

"""

indegree = [0] * len(graph)

queue = []

topo = []

cnt = 0

for key, values in graph.items():

for i in values:

indegree[i] += 1

for i in range(len(indegree)):

if indegree[i] == 0:

queue.append(i)

while queue:

vertex = queue.pop(0)

cnt += 1

topo.append(vertex)

for x in graph[vertex]:

indegree[x] -= 1

if indegree[x] == 0:

queue.append(x)

if cnt != len(graph):

print("Cycle exists")

else:

print(topo)

# Adjacency List of Graph

graph = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [], 5: []}

topologicalSort(graph)

Sunbelt Computer Software