（初級者競プロer向け）グラフの探索(DFS)を1から再帰関数で実装する方法

前回の記事にてグラフのおおよその実装の仕方は分かったと思います。
前回の記事→（初心者向け）グラフの実装について - bplain’s blog

今回は、そのグラフを探索する操作の書き方です。

そして今回の記事は、再帰関数をN=0からインクリメントしてN=3で終了とすると、その動き方は0123210となっている事を知っている人を対象としています。
逆に言うと前回の記事とそれだけ知っていれば十分読めるように作りました。
もし分からない場合はそれらを復習するとわかると思います。

１、直線で連結している形

まずはグラフが横に連結しているケースを考えます。(1-3-4-6-9など)
先にコードを見てみます。

#include <iostream>
#include <vector>

using namespace std;

vector<int>gragh[100];

void dfs(int v) {//vは現在いる頂点。次の頂点のgraph[v][0]を引数として受け取ることができる。
    cout << v << endl;
    if (gragh[v][0] == 9)return;//goal地点

    dfs(gragh[v][0]);//gragh[v][0]が次の引数として取り込まれる。(graph[v][0]=bを次の町として考えるときれいに成り立っている。）
}

int main() {

    int a = 1, b = 3;
    gragh[a].push_back(b);
    a = 3; b = 4;
    gragh[a].push_back(b);
    a = 4; b = 6;
    gragh[a].push_back(b);
    a = 6; b = 9;
    gragh[a].push_back(b);

    //1-3-4-6-9

    dfs(1);//スタート地点

}

前回、頂点aから頂点bに行くためには、隣接リストだと、gragh[a][i]=bと表せるということをやりました。

このとき、dfs(int a)という関数を用意しておいて、再帰でdfs(graph[a][0])と書くと、
引数aには行き先が取り込まれます。(graph[a][i]=b(bは行き先)のため。)

そしてコードが進むとその行き先はまたdfs(graph[a][0])により変数aに取り込まれます。

とりあえずここまでを理解するのがまずは重要です。よかったら上のコードで遊んでみてください

２、円状に連結している形（閉路）

次は連結で円状の形を考えます。1-2-3-4-5-6となってから、6-1と戻る形です。

この場合先ほどのDFSを用いて、1に着いたらフラグが立っていない確認をして、立っていなかったらフラグを立て、2に着いたらまたフラグの確認をしてフラグを立て・・・と順に行っていきます。
6番から1番に行く時に1番のフラグが立っていることを確認し、6番から1番以外への道を探します。今回はないので6番におけるループを脱出といった形です。そして5番の頂点からまたループに潜ります。(5-6は探索済みとなり次の辺を探そうとする)

コードに解説を徹底的に書きなぐったので、そちらを見ると分かりやすいかもしれません。

#include <iostream>
#include <vector>

using namespace std;

vector<int>graph[100];
bool visited[10];//到達済みのflag

void dfs(int v) {//vは現在地点。vからbに行こうとしている。
    if (visited[v])return;//すでに到達しているならば一番最後の関数を閉じ、一つ前の関数に戻る(endの位置)。
    visited[v] = true;
    
    for (int i = 0; i < (int)graph[v].size(); i++) {//それぞれの頂点のリストを0から確認し、行き先がないか判断する。
        cout << v << ' ' << graph[v][i] << endl;//現在いる頂点の出力用にどうぞ
        dfs(graph[v][i]);//graghの[v][i]=bが次の引数として取り込まれる。
        //end。頂点6のループ,5のループ...,4,3,2,1と戻っていく。
    }
}

int main() {

    int a = 1, b = 2;
    graph[a].push_back(b);
    a = 2; b = 3;
    graph[a].push_back(b);
    a = 3; b = 4;
    graph[a].push_back(b);
    a = 4; b = 5;
    graph[a].push_back(b);
    a = 5; b = 6;
    graph[a].push_back(b);

    a = 6; b = 1;
    graph[a].push_back(b);
    //   　6
    // ／      ＼
    //1--2--3--4--5 

    int V = 6;//頂点数
    for (int i = 1; i <= V; i++) {//頂点全てからdfsを試みる。
        if (visited[i] == false) {//頂点1から6までのフラグ。今回は頂点１から一回ですべてを回れてしまうのでi=1の時しか関数は呼び出されない
            dfs(i);
        }
    }
    cout << "YES" << endl;//動作終了
}

正直なところ、最初は無事動作を終えるプログラムを書くだけで難しいので、コピーしてお試しください。
そして再帰関数の終了の感覚をつかみにくい方は、思い切ってreturnの地点でgoto文を使っていると考えてしまうのが分かりやすくておすすめです。
そうして自分は理解することが出来ました。

この記事を書くのにいつもよりかなりの体力を要したので、今回はおしまい。
よかったらツイッターでふぁぼでもなんでも飛ばしてくださいな(ふぁぼが来ると普通に嬉しい）