質問編集履歴
2
最後の一文
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -85,3 +85,5 @@
|
|
|
85
85
|
|
|
86
86
|
|
|
87
87
|
このように，上記のDFS再帰では0→1→2→3の遷移しか生成できないように思えるのですが，どのようなことが起こっているのでしょうか．
|
|
88
|
+
|
|
89
|
+
（0→1→3→2のような遷移は生成されないのでしょうか？）
|
1
コードと図を追加しました．
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -30,6 +30,36 @@
|
|
|
30
30
|
|
|
31
31
|
}
|
|
32
32
|
|
|
33
|
+
|
|
34
|
+
|
|
35
|
+
int main() {
|
|
36
|
+
|
|
37
|
+
int N, M; cin >> N >> M;
|
|
38
|
+
|
|
39
|
+
|
|
40
|
+
|
|
41
|
+
Graph G(N);
|
|
42
|
+
|
|
43
|
+
for (int i = 0; i < M; ++i) {
|
|
44
|
+
|
|
45
|
+
int a, b;
|
|
46
|
+
|
|
47
|
+
cin >> a >> b;
|
|
48
|
+
|
|
49
|
+
G[a].push_back(b);
|
|
50
|
+
|
|
51
|
+
G[b].push_back(a);
|
|
52
|
+
|
|
53
|
+
}
|
|
54
|
+
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
seen.assign(N, false);
|
|
58
|
+
|
|
59
|
+
dfs(G, 0);
|
|
60
|
+
|
|
61
|
+
}
|
|
62
|
+
|
|
33
63
|
```
|
|
34
64
|
|
|
35
65
|
seen[v]で訪問したノードを管理していると思いますが，seen[v]=falseとする処理がありません．
|
|
@@ -39,3 +69,19 @@
|
|
|
39
69
|
なぜ上記のような再帰関数の実装が可能なのでしょうか．
|
|
40
70
|
|
|
41
71
|
（seenは深さごとにローカル変数のように読み込まれているのでしょうか．．．？）
|
|
72
|
+
|
|
73
|
+
|
|
74
|
+
|
|
75
|
+
質問がわかりずらいので補足させていただきます．
|
|
76
|
+
|
|
77
|
+
まず，下図のようなグラフに赤線で一番深くまで遷移したとします．
|
|
78
|
+
|
|
79
|
+
この時点ですべてのノードはseen=trueですよね．
|
|
80
|
+
|
|
81
|
+
|
|
82
|
+
|
|
83
|
+
そのあと，１のノードに戻ってノード３に遷移しようとしますが，seen[3]=trueのままです．
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
このように，上記のDFS再帰では0→1→2→3の遷移しか生成できないように思えるのですが，どのようなことが起こっているのでしょうか．
|