Depth First Search
Back to Problem Solutions forum
We have A(0) B(1) C(2) D(3) ......
- We push in the Stack 0
- Remove from the stack 0 as next element,marked it as seen.
- Push in the Stack all neighbors of A(0) , B C E (1 2 3) So we have in Stack 1 2 3 and 3 is last element
Remove from the stak 3 as top element, thus ,we must go from A(0)---->D(3) but in the problem example at this step we go from A(0)------> B(1)
Any clue ? or I am tottaly wrong here in understanding Algoritm ?
> I am tottaly wrong here in understanding Algoritm ?
No, the order of pushing neighbors do not make algorithm different. However for the sake of the checking your result we want some predetermined order.
I do not remember well, but here are words: To avoid ambiguosity please take care that neighbors should be tried in order of increasing their ids
I think that means that you should push neighbors to stack in reverse order, e.g. if you need to push BCE
then let E go in first and B last.
Dear Admin Just for checking:
Output result from the problem (www.codeabbey.com) I mean the corect one.
-1 0 1 9 19 14 16 29 2 31 15 34 4 5 20 7 12 32 21 8 10 39 36 24 30 22 39 4 11 6 37 25 34 17 3 39 13 26 23 33
We have here number 39 three times. In other words we have three vertices visited from vertice number 39. It this is possibel ?
Very strange situation :) Acctually my cod generate the corect numbers until . let say number 35-36 and for remaining gives me wrong numbers for examle: corect answer: -1 39 13 5 8 14 0 15 6 18 7 22 16 3 10 4 27 9 2 11 29 20 24 12 17 32 34 21 22 1 23 25 35 31 32 30 16 9 32 19 33 my answer: -1 39 13 5 8 14 0 15 6 18 7 22 16 3 10 4 27 9 2 11 29 20 24 12 17 32 34 21 36 1 23 25 35 31 40 30 38 28 26 19 33
I tried several times and the same shit. The last 5-6 numbers do not match the corect answer :(
-1 39 13 5 8 14 0 15 6 18 7 22 16 3 10 4 27 9 2 11 29 20 24 12 17 32 34 21 22 1 23 25 35 31 32 30 16 9 32 19 33
-1 39 13 5 8 14 0 15 6 18 7 22 16 3 10 4 27 9 2 11 29 20 24 12 17 32 34 21 36 1 23 25 35 31 40 30 38 28 26 19 33
> In other words we have three vertices visited from vertice number 39. It this is possibel ?
Yes, I think - it is like a tree - we traverse from 39 until there is no more way, then return here and try some other direction.
> The last 5-6 numbers do not match the corect answer
Usually this mean that you have correct part of algorithm for going forward through vertices, but when you came to dead end, your back-track part (returning to vertex where there are another ways, like 39) may have some mistake.
You are absolutely right. Now i have to invent something in order to keep the track from where i comming.
hello. let us see example once more.
We have A(0) B(1) C(2) D(3) E(4) F(5) G(6)
We push in the Stack 0
Remove from the stack 0 as next element,marked it as seen.
Push in the Stack all neighbors of A(0) , B C D (1 2 3) in reversed order (becouse - To avoid ambiguosity please take care that neighbors should be tried in order of increasing their ids )
So we have in Stack 3 2 1 and 1 is last element (LIFO)
Remove from the stak 1 as top element, we go from A(0)---->B(1)
Marked B(1) as seen
Puss in Stack all neighbors of B(1) - E(4), A(0)in reversed order
We have in Stack 3 2 4 0
0 is seen, and next way must be B(1) --> E(4) !
so the path will be A(0) --> B(1) --> E(4) --> D(3) --> C(2) --> F(5) --> G(6)
and "path from" should be -1, 0, 1, 4, 3, 2, 5
but in example - -1 0 3 4 1 2 5
Where is mistake?
Hi Viach,
As you said "the path will be A(0) --> B(1) --> E(4) --> D(3) --> C(2) --> F(5) --> G(6)"
and the answer is -1 0 3 4 1 2 5 because...
To get to position 0 you come from -1
To get to position 1 you come from 0
To get to position 2 you come from 3
To get to position 3 you come from 4
To get to position 4 you come from 1
To get to position 5 you come from 2
To get to position 6 you come from 5
thank you!
algorithm was right, but I d'nt understand what sрould be in output.
problem is solved!