algorithmgraph-algorithmdirected-acyclic-graphstopological-sort

Topological sorting of a directed acyclic graph into stages

Is there an algorithm that, given an unweighted directed acyclic graph, sorts all nodes into a list of sets of nodes such that

  1. the topological order is preserved (i.e., for all edges u->v, v occurs in a set further down the list than u) and
  2. the length of the list is minimal.

Is there a name for this problem?

Example

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]

enter image description here

Solution

  • Consider this variation of the canonical Kahn's algorithm:

    1. Start with a set `S_0` containing all nodes with no incoming edges

      2. Starting with n = 0:

    2. Initialize the next set `S_n+1`
    3. For each `n` in `S_n`:
      1. For all successors `d` of `n`, remove the edge `n -> d`
      2. If `d` has no other incoming edges add it to `S_n+1`
    4. If `S_n+1` is not empty, increase pass to n+1 and repeat from 2.

    The list of S_0 ... S_k sets contains the result.