data structures - What is the correct order after topological sort? - Stack Overflow

admin管理员组

文章数量:1405156

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

Share Follow edited Mar 9 at 6:44 greybeard 2,55599 gold badges3838 silver badges7070 bronze badges asked Mar 9 at 3:20 unknown potato pumbaunknown potato pumba 2111 silver badge22 bronze badges 3

• 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

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

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.

本文标签： data structuresWhat is the correct order after topological sortStack Overflow