Search code examples
directed-acyclic-graphstopological-sort

DAG and Top Sort

"Arranging the vertices of a DAG according to increasing pre-number results in a topological sort." is not a true statement apparently, but I'm not seeing why it isn't. If the graph is directed and doesn't have cycles, then shouldn't the order in which we visit the vertices necessarily be the correct order in which we sort it topologically?

Solution

  • Arranging by increasing pre-number does not guarantee a valid topological sort. Consider this graph:

        A
    ↓
B → C → D

    The two valid topological orders of this graph are:

    A, B, C, D
B, A, C, D

    If you were to visit the nodes beginning with C, one possible pre-number order would be:

    C, D, A, B

    That is not a valid topological order. An even simpler example is this graph:

    B → A

    There is clearly one valid topological order, but if we were to visit A first and sort by pre-number, the resulting order would be backwards.