Javalobby - Comments for "Algorithm of the Week: Topological Sort Revisited"
http://architects.dzone.com/articles/algorithm-week-topological-0
Comments for "Algorithm of the Week: Topological Sort Revisited"en Good point; that is a good
http://architects.dzone.com/articles/algorithm-week-topological-0#comment-91919
<!--paging_filter--><p> Good point; that is a good way of doing it. <br /></p>Wed, 19 Dec 2012 09:42:56 -0500acoincomment 91919 at http://java.dzone.comThe loop in your pseudo-code
http://architects.dzone.com/articles/algorithm-week-topological-0#comment-91903
<!--paging_filter--><p>The loop in your pseudo-code only removes nodes from the queue but never adds to it, as it should :) If corrected, it will be an instance of a breadth-first graph traversal.<br />But in fact a better option is to do depth-first traversal. Start with an empty list T, and for each node with no predecessors initiate a DF traversal. Each time you abandon a node because it has no non-visited successors, add that node to the front of T. When you are done, T is a topologically sorted list of the nodes of the graph. This algorithm runs in linear time and needs no additional space except 1 bit per node to keep track of the visited nodes.<br /><br /></p>Wed, 19 Dec 2012 06:45:58 -0500boykobbcomment 91903 at http://java.dzone.com