Kahn algorithm to do topological sorting in an undirected graph

Kahn Algorithm

Kahn algorithm is to do topological sorting in a directed graph. We need to calculate indegree of each node After removing all indegree if for any node indegree is still left it means there is a cycle, for topological sorting, graph should not be cyclic. Note : To start with topological sorting we need to start with a node whose indegree is ZERO

1. Initialize a queue, nodes with indegree should be first inserted to queue
2. Pop the node with indegree zero and visit its neighbour, decrease the indegree of its neighbour , one of the neighbour will become zero add that to queue.
3. Keep poping from queue till queue becomes empty.

Example problems which can be solved : Course Schedule : Given courses and its dependent courses print the order in which you should take courses so that you finish them Parallel Courses : Given courses and its dependent courses, in how many semesters will you take to finish them all

TotalValue