Depth First Search

Back to Problem Solutions forum

Vladimir_V     2015-07-24 12:57:25

We have A(0) B(1) C(2) D(3) ......

  1. We push in the Stack 0
  2. Remove from the stack 0 as next element,marked it as seen.
  3. 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
  4. 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 ?

Rodion (admin)     2015-07-24 13:19:20
User avatar

> 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.

Vladimir_V     2015-07-24 16:31:37

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 ?

Vladimir_V     2015-07-24 16:45:13

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 :(

Vladimir_V     2015-07-24 16:46:17

-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

Rodion (admin)     2015-07-24 17:13:22
User avatar

> 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.

Vladimir_V     2015-07-24 19:03:03

You are absolutely right. Now i have to invent something in order to keep the track from where i comming.

Viach     2016-07-14 07:43:44

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?

Quandray     2016-07-14 08:28:47
User avatar

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

Viach     2016-07-14 09:22:23

thank you!
algorithm was right, but I d'nt understand what sрould be in output.
problem is solved!

Please login and solve 5 problems to be able to post at forum