DFS: confirmations please.
Michelle Mok
means we cannot use the code for DFS listed in the book (is this correct?)
The on-line handout for graphs has example traversals for both the
recursive version and the stack version. They are different, meaning that
a different implementation of the traversal will result in incorrect
autotests. (is this correct?)
Are the test cases posted for the recursive version at the moment? Because
the book's code is compatible with autotest, while a non-recursive version
is not. Has anyone else noticed this? IS THIS CORRECT?
Should I use a non- recursive implementation as the reply said? or a
recursive one and pass?
mm
Parayandeh Amir
Michelle is right, the problem is that we always have to visit the
smallest-numbered vertex first, this doable easily if we use recursion for
DFS , but with using stack it is more complicated. The problem statement
does not indicate that we HAVE to use stacks so can we use recursion ?
Amir
John Wu
>
> Michelle is right, the problem is that we always have to visit the
> smallest-numbered vertex first, this doable easily if we use recursion for
> DFS , but with using stack it is more complicated. The problem statement
> does not indicate that we HAVE to use stacks so can we use recursion ?
>
Technically, both implementations are achievable. Whether both are
acceptable for the assignment, I think Tarek's posting has already
answered that. If you still want to make sure, I suggest you to confirm
with your instructors again, as they will have the final say.
.--------..------------..--------..-----------------------..--------.
| o\ /o || John C Wu || o\ /o || Engineering Science || o\ /o |
| ---- || || ---- || University of Toronto || ---- |
`--------'`------------'`--------'`-----------------------'`--------'
"Memory is like an orgasm. It's a lot better if you don't have to fake it."
Seymour Cray commenting on virtual memory
John Wu
> the reply to Sleeples Nights said not to use recursion. I am assuming that
> means we cannot use the code for DFS listed in the book (is this correct?)
I do not know what code is in the book. But according to a previous
posting by the Prof, you should not use recursion.
> The on-line handout for graphs has example traversals for both the
> recursive version and the stack version. They are different, meaning that
> a different implementation of the traversal will result in incorrect
> autotests. (is this correct?)
>
It is POSSIBLE to get identitical results for the stack implementation and
the recursion implementation of DFS. I implemented both, and both passed
autotests. The hint is that the stack version should behave exactly like
the recursion version, which requires a bit of additional thinking. Try
to use autotest case #2 as an example and do a manual tracing, and it
should help you.
> Are the test cases posted for the recursive version at the moment? Because
> the book's code is compatible with autotest, while a non-recursive version
> is not. Has anyone else noticed this? IS THIS CORRECT?
>
Both versions can pass autotest, if you implement your stack
implementation of the DFS correctly.
erik watson-hurthig
> the recursion implementation of DFS. I implemented both, and both passed
> autotests. The hint is that the stack version should behave exactly like
> the recursion version, which requires a bit of additional thinking. Try
> to use autotest case #2 as an example and do a manual tracing, and it
> should help you.
>
> > Are the test cases posted for the recursive version at the moment? Because
> > the book's code is compatible with autotest, while a non-recursive version
> > is not. Has anyone else noticed this? IS THIS CORRECT?
> >
>
> Both versions can pass autotest, if you implement your stack
> implementation of the DFS correctly.
>
[snip]
this is crazy! the assignment sheet tells one to do a BFS followed by a
DFS, and makes no mention how to do this. I hope this means style points
are awarded the same regardless of how you do it ( within reason )
erik "feed the flames" watson