Is there an algorithm that, given an unweighted directed acyclic graph, sorts all nodes into a list of sets of nodes such that
u->v
, v
occurs in a set further down the list than u
) andIs there a name for this problem?
A possible sort for the graph below would be
[1], [2, 3], [4, 5], [6, 7]
An alternative solution would be
[1], [2, 3], [4], [5, 6, 7]
Consider this variation of the canonical Kahn's algorithm:
Starting with n = 0:
The list of S_0 ... S_k
sets contains the result.