DFS works fine with example but still fails (Task 155)
Back to Problem Solutions forum
Hey!
Could you please provide one more example for the 'Depth First Search' problem,please?
I cannot find error in my code.
For example,sample from the page works fine with my solution:
But for common case I noticed incorrect values due to validation,for example
Failed example:
DepthFirstSearch(48,123,[[45,28],[7,13],[8,20],[9,22],[5,43],[13,37],[33,6],[23,30],[3,16],[13,26],[41,19],[40,25],[9,0],[39,42],[43,20],[33,4],[7,42],[24,21],[30,11],[14,38],[32,25],[28,29],[47,36],[0,39],[20,1],[13,46],[32,11],[10,17],[28,8],[18,41],[33,27],[37,21],[40,11],[17,45],[13,34],[14,16],[37,42],[30,47],[18,5],[32,44],[15,7],[16,28],[9,33],[35,3],[34,36],[6,28],[46,9],[21,36],[9,40],[2,9],[39,17],[43,12],[43,15],[31,35],[0,47],[12,15],[9,44],[2,31],[25,6],[10,5],[24,1],[11,5],[8,12],[43,1],[28,19],[15,14],[29,20],[40,13],[4,31],[5,26],[32,22],[20,7],[30,21],[29,36],[36,7],[45,24],[28,13],[13,24],[0,29],[30,41],[34,24],[38,39],[18,46],[22,26],[29,27],[19,44],[10,45],[39,7],[26,23],[8,2],[41,17],[40,37],[9,43],[20,15],[44,23],[2,44],[15,37],[20,34],[15,36],[31,21],[30,8],[29,34],[38,26],[23,3],[19,16],[40,46],[27,22],[23,42],[26,25],[46,32],[36,35],[35,7],[24,26],[39,34],[44,46],[36,18],[24,23],[11,33],[45,15],[47,44],[34,19],[2,37],[0,38]])
Expected:
[-1,24,9,16,33,26,25,15,2,0,5,30,8,7,16,12,19,10,36,34,1,31,27,3,13,32,22,29,6,20,23,4,11,6,39,36,21,40,14,17,46,18,37,5,46,28,18,44]
Got:
[-1,24,9,16,33,26,25,15,2,0,5,30,8,7,35,12,19,10,36,34,1,31,27,3,13,32,22,29,6,20,23,4,11,45,39,47,21,40,14,17,46,18,37,38,42,28,41,44]
I've tried to implement both solutions from Wikipedia page,and both solution produces exactly the same result.
Could you have a look on that issue,please?
Thanks in advance and looking forward for your answer!
Mikhail, Hi!
Thanks for your question! I'll try to investigate the problem and write back soon.
Hi again!
I'm afraid your algorithm has a minor problem with tracking back from terminal nodes. Note that your
answer says we have visited the node 33 from 45 while there are no direct edge between them. All others
discrepancies are of the same kind.
Below there is more thorough explanation.
I recreated the map of the graph from your data: http://pastebin.com/8u9uUt6P
and then I started to traverse it with pencil and paper from 0-th node each time choosing the neighbor
with the least id.
All goes quite well until you reach node 45 which is terminal (it have no unvisited neighbors) and we
need to track back. This chain looks like this:
0 -> 9 -> 2 -> 8 -> 12 -> ... -> 25 -> 6 -> 28 -> 45
We return to node 28 but it also have no more unvisited neighbors. Then we go to
node 6 and from there the next (and only) unvisited neighbor is 33.
Note that your answer tells that we go to 33 directly from 45, which is not correct (there are no
edge between them). There should be 6 instead.
Hope this may help! Please feel free to write if my explanations are not clear enough.
BTW You are right, the example in the problem statement is not sufficient since it lacks terminal nodes at all. I'll add another, simpler one. Thank you for pointing this out!
Hey Rodion,
All is clear now. Just rewrote my solution a bit and got the pass score. :-)
Thanks a lot for your time and your help! Mike