JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Introduction to graphs and their data structures Why hasn't DFS been corrected?
 Why hasn't DFS been corrected? | Reply I was going to point out the DFS iterative algorithm doesn't work, but I see I'm 5 years too late. Why hasn't it been corrected? did it revert or something?The section would be much clearer if two approaches were explained separately - visiting all nodes (as a flood-fill needs to do) versus visiting all paths. The iterative and recursive solutions for all nodes could be presented, then a single line change in the recursive solution could be used for all paths and one could either point out the difficulty of doing the same thing iteratively or provide the more awkward iterative sol'n:stack choices, path;node here;push(choices,start);while (here= top(choices)) {push(here, path);check exit conditions;for all neighbors(here) not in path push(neighbor,choices);while top(path) == top(choices) pop(path), pop(choices) //backtrack}
 Forums Tutorial Discussions Introduction to graphs and their data structures Why hasn't DFS been corrected? Previous Thread  |  Next Thread