再帰関数でのDFSの実装

Question

下記のような再帰関数でのDFSの実装について質問です．

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true;

    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v);
    }
}

int main() {
    int N, M; cin >> N >> M;

    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    seen.assign(N, false);
    dfs(G, 0);
}

seen[v]で訪問したノードを管理していると思いますが，seen[v]=falseとする処理がありません．
感覚的には，これでは一度訪問したノードはtrueとなり続け，いちばん深くまでたどったあとに遡って別の分岐をおこなおうとした際にcontinueになってしまうノードが出てきてしまうように思います．
なぜ上記のような再帰関数の実装が可能なのでしょうか．
（seenは深さごとにローカル変数のように読み込まれているのでしょうか．．．？）

質問がわかりずらいので補足させていただきます．
まず，下図のようなグラフに赤線で一番深くまで遷移したとします．
この時点ですべてのノードはseen=trueですよね．

そのあと，１のノードに戻ってノード３に遷移しようとしますが，seen[3]=trueのままです．

このように，上記のDFS再帰では0→1→2→3の遷移しか生成できないように思えるのですが，どのようなことが起こっているのでしょうか．
（0→1→3→2のような遷移は生成されないのでしょうか？）

Comments

[ohys]

プログラムの全体像が見えないのですが、dfs関数を実行する前にseenはfalseで初期化するものだと思います。質問に載せていないところでそういった処理をしているのではないでしょうか？

[hakubo2]

回答ありがとうございます．
コード全体を載せて修正しました．
質問も不親切でしたので，図を追加しています．
教えてくださると幸いです．

Answer 1

なにか根本的に勘違いしていると思うのですが、
一度通ったノードはもう探索する必要がないので、別の分岐で通る場合を考慮する必要が無いときに使うのが、深さ優先探索です。

Comments

[hakubo2]

目的から勘違いしていたんですね．
DFSでハミルトンパスを求めようとして，混乱したようです．
ありがとうございました．