Search code examples
algorithmsortingpseudocodetopological-sort

Determining whether a directed graph has a unique topological ordering?

I'm trying to design an algorithm to determine whether a directed graph has a unique topological ordering. Anyone know how to write pseudo-code for this?

Solution

  • Recall the procedure of the topological sort, which is in short:

    1. result <- [] //empty list
    2. Find a node n which is a sink in the graph
    3. remove all edges connecting to n, and n from the graph
    4. result.addFirst(n)
    5. if there are nodes left, return to 2

    If at any iteration, at step 2 you have a choice to pick 1 from 2 or more nodes, the topological sort is not unique. If at any point, you are stuck before exhausting the graph - there is no topological sort at all.