GeezerVison is showing github.com — Python-3/graphs/kahns_algorithm_topo.py at master · https-github-com-nzysoft/Python-3

Expand file tree

kahns_algorithm_topo.py

Copy path

More file actions

36 lines (30 loc) · 817 Bytes

Copy path

36 lines (30 loc) · 817 Bytes

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

def topological_sort(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 values in graph.values():

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: []}

topological_sort(graph)