CODEWITHSUNDEEP
algorithmdata-structuresgraphgraph-theorytopological-sort
verticese
verticese

Reputation: 273

How to find if a directed graph has two topological ordering?

After I learned how to determine if a directed graph has 1 topological ordering, I am sort of curious if there is a way to determine if there are graphs with exactly 2. First of all is it true that there are graphs with 2 topological sorts?

I learned to use a Hamiltonian path to determine if a DAG has a unique topological sort. Does that somehow apply to this? Thanks

Upvotes: 2

Views: 2313

Answers (1)

Andrey Taptunov
Andrey Taptunov

Reputation: 9525

If at the line (*) you can select from 2 different nodes once - there are two topological orderings

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S (*)
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

More precisely quoting R. Sedgewick:

A digraph has a unique topological ordering if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path). If the digraph has multiple topological orderings, then a second topological order can be obtained by swapping a pair of consecutive vertices.

Upvotes: 4

Related Questions