kahns_algorithm_long.py

# Finding longest distance in Directed Acyclic Graph using KahnsAlgorithm
deflongest_distance(graph):
indegree= [0] *len(graph)
queue= []
long_dist= [1] *len(graph)

forvaluesingraph.values():
foriinvalues:
indegree[i] +=1

foriinrange(len(indegree)):
ifindegree[i] ==0:
queue.append(i)

whilequeue:
vertex=queue.pop(0)
forxingraph[vertex]:
indegree[x] -=1

long_dist[x] =max(long_dist[x], long_dist[vertex] +1)

ifindegree[x] ==0:
queue.append(x)

print(max(long_dist))


# Adjacency list of Graph
graph= {0: [2, 3, 4], 1: [2, 7], 2: [5], 3: [5, 7], 4: [7], 5: [6], 6: [7], 7: []}
longest_distance(graph)