Test yourself
Consider the following graph..
Whicho of the following points can not come first in a generated topological order ?
Which of the following would be a valid topological sort ?
Kahn's algorithm is used to topologically sort a given graph.
Topological sorting is a non-unique ordering of a graph's vertices such that if there is directed edge between A and B, then A must come before B in the ordering.
1) Identify a node of the graph which has an indegree of zero.
The indegree of a node is defined as the number of edges going into the node.
2) Add the node to the end of the current topological order.
3) Remove the node from the graph.
4) Keep repeating steps 1 to 3 until all vertices have been added to the topologically sorted list.