StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs Topological Sorting trying to sort vertices or edges?
text
Body
copied!<p>Happy easters, everyone. </p> <p>I am currently learning topological sort and having a question about what topological sort tries to really sort.</p> <p>The <a href="http://www.algorist.com/" rel="noreferrer">Algorithm Design Manual</a> describes topological sort in this way: </p> <blockquote> <p>Topological sorting is the most important operation on directed acyclic graphs (DAGs). <strong>It orders the vertices on a line such that all directed edges go from left to right.</strong></p> </blockquote> <p>This bold part confuses me. So does the topological sorting sort vertices or all directed edges?</p> <p>Let's take an example which is also in the book.</p> <p><img src="https://i.stack.imgur.com/fdJBN.png" alt="A DAG"></p> <p>So for the above DAG, we can get a topological sort (G, A, B, C, F, E, D).</p> <p>I can understand this sort. Not only the vertices are sorted, but the edges are also sorted, i.e., G->A->B->C->F->E->D, this matches the above ADM book description: <code>all directed edges go from left to right</code></p> <p><strong>But what if I remove the edge of B->C?</strong> The resulting graph is still a DAG, but will the topological sort is still (G, A, B, C, F, E, D)? </p> <p>If it is Yes, then I think the edges are not sorted, as A->B->C does not exist any more, instead, it is A->B and A->C. So, it this case still a valid topological sort? Can we still think (G, A, B, C, F, E, D) is a valid sort even if A is the parent of B and C?</p> <p>Thanks</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload