depth first search

I agree, it seems to me the task condition not enoughs some important information, details. How the hell we pick the first node? I thought it must be the 0-th, but it isn't. Let's take a look to the given algorithm:

1. We add the initial node to stack. ===> Okey, no problem
2. Remove the next element from the stack and call it current. ===> Ok, it will be node "-1"
3. If the current node was seen then skip it (going to step 6). ===> Ok
4. Otherwise mark the current node as seen. ====> Ok, marked this node
5. Get all neighbors of the current node and add all them to stack. ====> Which neighbors!? Node "-1" has no neighbors. Logical dead-end...
6. Repeat from the step 2 until the stack becomes empty. ====>....

Why "-1 0 1 4 3 2 5" its not a correct answer for the given example?

I belive, I miss something or missunderstood conditions of the problem. Give some hint, please. Thanks.

The first node is not -1 as there is no such node. Note that the '-1' in the example answer does not refer to the 0-th node visited but rather the node from which the 0-th node was visited - that's not the same thing!

Ok, then which node will be the first?
Perhaps, in case with the example data, the first node will be taken it's from the first pair "0 1" => 0, right? If it so, that means we can get around given tree in different ways:

• -1 0 3 2 5 1 4
• -1 0 3 4 1 2 5
• -1 0 3 2 5 1 4
• -1 0 2 5 3 1 4
• -1 0 2 5 1 4 3
• -1 0 1 4 3 2 5

I don't get it( Why the right sequence exactly like this -1 0 3 4 1 2 5? Lets start from 0.

-1 0...

In list of edges we have 3 connections to 0 - [1, 2, 3]. Ok, lets take the next node by LIFO.

-1 0 3...

So, current node 3 has connections [0, 4, 2, 6]. Adding them to stack [1, 2, 0, 4, 2, 6]. How did we come at 4 after 3???

Quote from the first example: "This example is relevant to the graph represented in the picture, but letters are substituted with the integers."

Spanning tree for this example: A B E D C F G Or with integers: 0 1 4 3 2 5 6

You visit 0 coming from -1 (-1 is a dummy entry as 0 is the first node of the spanning tree)

You visit 1 coming from 0

You visit 2 coming from 3

You visit 3 coming from 4

You visit 4 coming from 1

You visit 5 coming from 2

You visit 6 coming from 5

Now have a look at the second column of numbers above ...

Thanks, I've got a few steps closer to solution. And it worked on both examples data. But it doesn't work for the real data. In what order should I walk around nodes?

By the condition I have this:

44 109
31 37
14 24
21 7
3 32
18 25
39 13
37 34
41 8
7 16
28 30
27 36
16 36
4 9
14 25
2 4
39 12
18 12
16 34
10 6
40 28
11 3
2 12
17 23
38 7
16 11
24 3
30 27
17 43
30 16
24 8
40 42
19 5
17 36
23 11
29 21
6 0
42 10
5 21
42 37
29 28
4 11
1 39
23 19
38 22
1 19
34 0
18 6
16 0
31 4
31 25
33 14
31 5
8 27
30 13
15 42
26 1
35 39
33 20
20 38
31 30
29 14
14 35
29 19
43 15
24 40
32 39
28 22
4 34
11 7
0 30
26 20
0 26
19 42
13 6
17 9    
22 25
35 3
36 30
3 43
18 11
26 19
8 17
41 21
38 36
18 9
37 30
22 32
38 15
12 27
4 43
2 6
41 5
5 36
24 12
32 18
33 31
15 0
1 21
41 3
15 20
13 31
41 9
6 28
37 10
43 26
40 39
38 0
5 12
28 38

So lets start from 0:

• node 0 has some neighbours [-1, 6, 34, 16, 30, 26, 15, 38] => lets take first [-1] - ok
• next node 1 has neighbours [39, 19, 26, 21] => takeing first? [39] - wrong! takeing last? [21] - wrong! the right will be [19]! how is this happend?
• next node 2 has neighbours [4, 12, 6] => [4]? - no! we need [6]?
• next node 3 has neighbours [32, 11, 24, 35, 43, 41] => [32]? [41]? [11]? - all wrong! we need [24]!!!

and so on...

help me!

Vladimir, Hi!

I poorly remember this problem, but reviewing the statement I found the line:

To avoid ambiguosity please take care that neighbors should be tried in order of increasing their ids (like in BFS problem).

So starting from 0 you should look at neighbors here - the smallest unvisited is 6 (no reason to look into -1 I guess). From 6 you look at unvisited neighbors again and pick smallest of them (probably 2 if I'm not mistaken) and so on.

With stack this means you should push neighbors in reverse order (so that when it comes to pop, you got the smallest unvisited neighbor first).

No sense in looking at nodes in arithmetical order (0, 1, 2, 3...) since it doesn't correspond with your way of traversing the tree.

Thank you, finally I've got it!