depth first search

[Andrew Tsao]

Hi,

I was just wondering if it's okay if our depth first search does not
involve a stack? Thanks.

[Robert Escriva]

I would find it very difficult to implement a DFS that does not have
some notion of the previously visited edges. Even a recursive
implementation has a stack. Beware though, you may overflow the stack
on larger graph components if done naively.

-Robert

[Andrew Casey]

And how might one fix this naive implementation? I am getting a Stack Overflow on the Large graphs and was thinking of implementing some type of maximum depth to limit how deep you recurse. However, I'm unsure as to how to do this while ensuring I still reach every possible Node, or if there's a better way to achieve the desired result.

--
Andrew Casey
Class of 2014

[Chaoran Song]

I just wanna clarify something, we don't actually have to implement a
stack if we're just using recursion right?

[Andrew Casey]

I believe that's what his answer implied. Recursive calls get pushed onto a stack to execute, so while you may not make one, Java is. Also, if a TA comes back to this post, I believe I figured out my own question in this thread so I don't need an answer.

[Sara Boccabella]

Andrew,
Can you explain or hint at how you stopped the stack overflow? I can't think of anything!

Thanks!

Sara

[Nikos Karampatziakis]

On Sun, May 1, 2011 at 5:08 PM, Andrew Casey <acc...@cornell.edu> wrote:
> And how might one fix this naive implementation? I am getting a Stack
> Overflow on the Large graphs and was thinking of implementing some type of
> maximum depth to limit how deep you recurse.

I think if you do this you can't claim that you are doing a depth
first search. In DFS you first have to go as deep as possible.

-Nikos

[Andrew Casey]

Sara,

I guess without saying too much I ended up implementing an iterative DFS instead of using recursion. Hope you figure it out!

Nikos,

That's the conclusion I came to, thanks. I figured it out another way.

[Robert Escriva]

Using recursive DFS will often lead to a stack overflow.

The best solutions are to manually manage the stack, or use BFS.

-Robert