Talk:Depth-first search
From Wikipedia, the free encyclopedia
Contents |
[edit] Wierd Example
Another more basic example should be given to start with, without the link from F to E. Surely it would be more intuitive to put the letters in a different order Something like
A
B C D
E F G
Or maybe the order that the search would go?
A
B E G
C D F
Opticyclic 16:33, 21 April 2006 (UTC)
I think the psuedocode give in incorrect-- it enters an infinite loop! the node must be marked as visited BEFORE recursively calling dfs on adjacent nodes. pleaes confirm this! Yonestar 17:26, 20 April 2006 (UTC)
What's with the "ie where's the recursion?" DFS doesn't require recursion... no algorithm does. The stack makes it so you don't have to recurse (that's all recursion really does for you anyway, is add to a stack). If lack of recursion is the only "problem" with the algorithm, then there is no problem.
Changed from "DFS is optimal" to "DFS is not optimal". Please Confirm.
can you show me the program in c for dfs
Whoever "corrected" the page to put E on the end of the path, please do not un-correct it again. DFS will follow the link from F to E before getting to E from A. The apparent tree view does not reflect the actual DFS tree, and I chose it that way deliberately for didactic purposes. Jerf
Can you explain what all non-negative path costs is refering to ?
DFS's can be preformed for graphs in general as well, not just Trees. Though if you're thinking specifically of the technique as used in state-space search's I guess not. Perhaps, these two concepts should be seperated? Deepak 01:39, 17 Jan 2004 (UTC)
They're awfully closely related... I've tried to improve the situation in my last edit, but there still needs to be some more seperation of "depth-first traversal" and "depth-first search". Jerf
Why does the page say that DFS is a method for traversing trees, and then goes on to give an example of a general graph? (as it clearly has a cycle it is not a tree). The page should either state that it is a method for traversing graphs, or change the example to a tree.
[edit] The algorithm given in pseudocode section is wrong?
Well, headline explains it all. It is not depth first for a general graph because of the Color(grey) thing.
I think the color(grey) thing shouldn't be there. and, there should be a color check just after the pop, to skip the node or not.
also, for generalization of the alg. to graphs, there should be an iteration over the nodes above the while loop. I'll change the pseudocode, if anyone has objections, we can revert it.
[edit] Recursive solution?
Why do we have TWO solutions, both of them iterative, creatings stacks, etc? It seems that in general, iterative approaches that have to heavily-manipulate stacks are well-suited to recursive approaches (at least - it is conceptually easier) - and that is certainly true here. I'm definitely going to replace one of these algorithms with a recursive solution. I'd prefer to replace the second, it looks less intuitive. (Remember we're not here to give the best-optimised code, but to teach how it works - therefore the conceptually easier code is always the best on wikipedia). —EatMyShortz 11:46, 28 February 2006 (UTC)
[edit] Pseudocode!=Python
As much as I love python, it shouldn't be marked as pseudocode. The second one was better, but still not pseudocode.
[edit] Applications
I miss applications of DFS here. Can anyone point to some algorithms, where it is used? --Pukeye 10:04, 28 August 2006 (UTC)
