Unique Topological Sort for DAG I have a DAG (directed acyclic graph) which has more than one valid topological sorting. I'm looking for a way to sort it topologically and always get the same, well defined result.

For example take this graph:

A--&gt;B
A--&gt;C
B--&gt;D
C--&gt;D


There are two solutions to a topological sort:

1: A, B, C, D and
2: A, C, B, D


We notice that B and C can be sorted in any order. Therefore we choose alphabetic sorting as secondary sorting to get only one solution: A, B, C, D.

Here's an other example:

E--&gt;G
E--&gt;H
H--&gt;F


There are three solutions to a topological sort:

1: E, G, H, F
1: E, H, G, F
3: E, H, F, G


But here, there's no obvious solution. No solution seems to be more "alphabetic" than the others.

Is there a way to get a unique, deterministic solution for any DAG?
If you are programming the sort algorithm, unless you use a random choice of the child of a parent node, your algorithm will always return the same answer. In your example, make a program that, starting from E, will prefer G to H and so forth. It will always answer E, G, H, F.
EDIT : here is the algo.  

While there is a vertex in the graph do
    Display the vertex with 0 incoming edge (if many choose the one with lower lexical order)
    Remove it and its out-going links from the graph
end


The order is what the algo displays.
It will start with E. It is displayed and removed. Then G and H are candidates. The one with the lower lexical order is G. It is displayed and removed. The next candidate is H. It is displayed and removed. Then F is displayed and removed.
The algo make a breadth-first search. Its display is E, G, H, F.
No. The Wikipedia article on topological sort does say that it's possible, in linear time, to determine whether a unique sort exists.