Editing Topological sort

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 59: Line 59:
 
The topological ordering will be unique if and only if <code>C</code> contains exactly one vertex at the beginning of each iteration of the while loop. The proof is left as an exercise to the reader.
 
The topological ordering will be unique if and only if <code>C</code> contains exactly one vertex at the beginning of each iteration of the while loop. The proof is left as an exercise to the reader.
  
''Theorem'': A topological ordering can also be obtained by running [[depth-first search]] and then reversing the postordering generated.
+
A topological ordering can also be obtained by running [[depth-first search]] and then reversing the postordering generated.
 
+
''Proof'': This is equivalent to the statement that if the edge <math>u-v</math> exists then <math>u</math> has a higher postorder number than <math>v</math>. So consider the DFS tree. If <math>u</math> is an ancestor of <math>v</math>, then <math>u</math> has a higher postorder number, as desired. If <math>u</math> is a descendant of <math>v</math> in the DFS tree, then a cycle exists from <math>u</math> back to itself, a contradiction. And if neither <math>u</math> nor <math>v</math> is an ancestor of the other, then <math>u-v</math> is a cross edge, and <math>u</math> has a higher postorder number, as desired. <math>_\blacksquare</math>
+
  
 
==External links==
 
==External links==
 
* {{SPOJ|PFDEP|Project File Dependencies}}
 
* {{SPOJ|PFDEP|Project File Dependencies}}
 
* {{SPOJ|DEPEND|Dependency Problems}}
 
* {{SPOJ|DEPEND|Dependency Problems}}

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)

Template used on this page: