Talk:Depth-first search

From Wikipedia, the free encyclopedia

Contents

[edit] Weird 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] Edges

The four tree edge types
The four tree edge types

The different classifications of edges are briefly discussed here, but should perhaps be moved to a new article. Consider:

  • Tree edge: an edge (u, v) where v was discovered by exploring edge (u, v);
  • Back edge: an edge (u, v) where u is connected to one of it's ancestors, v;
  • Forward edge: a non-tree edge (u, v) that connects a vertex u to a descendant v;
  • Cross edge: any other edge where one vertex is not an ancestor of the other.

I think this distinction should be made in the interest of better explaining the ability of detecting cycles in a graph using topological sorting. --Stimpy 20:10, 17 December 2006 (UTC)

By the way, cycle detection is not the same as topological sorting, and I'm not convinced it belongs in the topological sorting article at all any more than it would belong in articles about other algorithmic problems on DAGs. If it is there, it should be as a brief sentence explaining why the DFS based topological sort algorithm is correct rather than as a separate subsection. —David Eppstein 21:25, 17 December 2006 (UTC)
I'm sorry, upon reviewing my comment I understand that I didn't make clear what I was suggesting. I emphasize that (un)directional edges should be moved to a separate article and that both DFS article and the topological sorting article point to it, hence bridging the 'gap' in understanding how topological sort can be used – together with the principles of the four edge classifications – to find cycles in a depth-first search tree in O(n) time. In none of the articles on the subject is this relationship properly explained, in my opinion. —Stimpy 22:11, 21 December 2006 (UTC)

[edit] reverse postordering

Either the "reverse postordering" section has an error, or I am confused. Since "reverse postordering is the reverse of a postordering, i.e. a list of the vertices in the opposite order of their last visit", why is D not first in reverse postordering?

TJA —Preceding unsigned comment added by 68.162.149.237 (talk) 17:10, 25 March 2008 (UTC)