Can you solve and send me the original code which I can copy and paste plz. Thank you.

Kahn's Algorithm

Implement Kahn's Algorithm for giving a topological ordering of a graph as discussed in class. The input graph will be in adjacency list format.

1. Count the in-degree (number of edges ending at) each vertex.

2. Create a queue of nodes with in-degree 0.

3. While the queue is not empty:

a. Add the first element in the queue to the ordering.

b. Decrement the in-degree of each of the first elements neighbors.

c. Add any neighbors that now have in-degree 0 to the queue.

d. Remove the first element from the queue.

4. If the ordering doesn't contain all nodes then the graph had a cycle and we return None

5. Else we return the ordering

graph = [

[1, 3],

[],

[3, 6, 7],

[6],

[],

[],

[],

[5, 4],

]

order = topological(graph)

print(order)

[0, 2, 1, 3, 7, 6, 4, 5] # one POSSIBLE ordering

order.index(0) < order.index(3)

order.index(0) < order.index(1) 

order.index(2) < order.index(3)

order.index(2) < order.index(6)

order.index(2) < order.index(5)

order.index(3) < order.index(6) 

order.index(7) < order.index(5)

from collections import deque

#complete following code

def topological(graph): in_deg = [0 for _ in range(len(graph))] for node1 in range(len(graph)): for node2 in graph[node1]: in_deg[node2] += 1 queue = deque() """ Iterate over all the nodes and append the nodes with in-degree 0 to the queue """ # your code here ordereing = [] while len(queue) > 0: current_node = queue.popleft() ordereing.append(current_node)

for neighbor in graph[current_node]: in_deg[neighbor] -= 1 """ If this neighbor in-degree now becomes 0, we need to append it to the queue """

# your code here """ If we couldn't process all nodes, this means there was a cycle in the graph and the graph wasn't a DAG. """ if len(ordereing) != len(graph): return None return ordereing

order.index(7) < order.index(4)