FilesExpand file tree

 patch-2

/

kahns_algorithm_topo.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (27 loc) · 761 Bytes

 patch-2

/

kahns_algorithm_topo.py

Copy path

Top

File metadata and controls

• Code
• Blame

32 lines (27 loc) · 761 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

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

def topologicalSort(l):

indegree = [0] * len(l)

queue = []

topo = []

cnt = 0

for key, values in l.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 l[vertex]:

indegree[x] -= 1

if indegree[x] == 0:

queue.append(x)

if cnt != len(l):

print("Cycle exists")

else:

print(topo)

# Adjacency List of Graph

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

topologicalSort(l)