The task is to perform a topological sort of a graph with 7→5, 7→6, 5→2, 5→4, 6→3, 6→4, 2→1, 3→1, and 1→0:

The correct answer is given as [7, 6, 5, 4, 3, 2, 1, 0].

But why does 4 come first instead of 3 even though the degree of 3 becomes 0 first?
Could someone please explain it?

The task is to perform a topological sort of a graph with 7→5, 7→6, 5→2, 5→4, 6→3, 6→4, 2→1, 3→1, and 1→0:

The correct answer is given as [7, 6, 5, 4, 3, 2, 1, 0].

But why does 4 come first instead of 3 even though the degree of 3 becomes 0 first?
Could someone please explain it?

• data-structures
• directed-acyclic-graphs
• topological-sort
• digraphs

• Ah, I tried to edit the image to get it to render inline, but I couldn't quite get it. – Alexander Commented Mar 9 at 3:23
• 3 A graph can have multiple valid topological sorts. 4 can be anywhere later than 5 and 6 (and 7 by extension). 3 can be anywhere later than 6 (and again, 7 by extension). There is no dependency between 3 and 4, so they can appear in any order relative to each other. – Alexander Commented Mar 9 at 3:25
• My favourite analogy for topological sorts is to think about the order clothes are put on. Socks come before shoes, and shirts come before jackets. But there's no relationship between shoes and jackets. So long as you have your shirt and socks on first, you can put on your shoes and jacket in either order. – Alexander Commented Mar 9 at 3:27

1 Answer 1

There is no order between 3 and 4; topological order is a partial order (outside "linear" graphs).
Where there are unordered nodes, more than one linearisation is valid.
Any given one may be the result of a specific procedure; I take your the degree of 3 becomes 0 first to refer to one.