DFS(深さ優先探索)基本コードサンプルまとめ【C#】

お久しぶりです。
Atcoderをやり始めてそろそろ1年経つのですが、800-900あたりの緑ギリギリをさまよってます。

今回はAtcoder解いてて、あまりにDFS(深さ優先探索)のコードが書くのが遅い事に気づいたので、弱点克服学習兼、備忘録です。

自分がうまく解けなかった問題一例(2022-07-09 ABC259-D)

DFS使用例

DFSの考え方で扱える現実問題には色々あると思いますが、Atcoderではグラフや木の問題で使うことが多いと思います。

DFSとは？ってのはもっとスゴイ方がたくさん説明されてると思うので省きます。
今回参考にした記事だけ張っておきます。

参考:

グラフ移動可能問題

問題例:
グラフG(頂点N個) の二頂点 s,t∈V　が与えられたとき、si から辺をたどって ti に到達できるかどうかを判定する問題。

→s を始点とした DFS。
※有向グラフでも無向グラフでもそこまで変わらないので一緒に記載します。

// ここにグラフの接続状態を以下のようにセットする。(非接続:0)
// 有向グラフのとき：
// mapped[s,t] = 1  :  s→tと接続している。
// 無向グラフのとき：
// mapped[s,t]、mapped[t,s] = 1  :  s↔tと接続している。
var mapped = new int[N,N]; 
var seen = new bool[N]; //DFSで既に確認したフラグ
int si = 1;// スタート(仮)
int ti = 123;//ゴール(仮)

//下記のように使用
if (DFS(s))
    Console.WriteLine("Yes"); // si->tiは接続している
else
    Console.WriteLine("No");

//------------------------------------------
    bool DFS(int st)
    {
        seen[st] = true; //調査済
        if (st == ti) return true;//接続状態である

        for (int i = 0; i < N; i++)
        {
            if (seen[i]) continue; //既に調査済みのときは飛ばす
            if (mapped[st, i] == 1)
                if (DFS(i)) return true;//子が接続していることを発見した
        }
        return false;
    }

閉区間チェック

問題例:
グラフG(頂点N個) の二頂点 s,t∈V　が与えられたとき、si から辺をたどって 閉区間があるかどうかを答える問題。

→基本はさっきと同じ。
1つ前の値を保持ししておき「今来た辺を戻っていく動作」を禁止することで、閉区間チェックができる。

// ここにグラフの接続状態を以下のようにセットする。(非接続:0)
// 有向グラフのとき：
// mapped[s,t] = 1  :  s→tと接続している。
// 無向グラフのとき：
// mapped[s,t]、mapped[t,s] = 1  :  s↔tと接続している。
var mapped = new int[N,N]; 
var seen = new bool[N]; //DFSで既に確認したフラグ
var seen_finish = new bool[N]; //DFSで閉区間がないことを確認下フラグ

// 下記のように使用
if (DFS(s))
    Console.WriteLine("Yes"); // 閉区間がある
else
    Console.WriteLine("No");

//------------------------------------------
    bool DFS(int st, int bf = -1)
    {
        seen[st] = true; //調査済

        for (int i = 0; i < N; i++)
        {
            if (i == bf) continue; // 逆流禁止
            if (seen_finish[i]) continue; // 確認済スルー
            if (mapped[st, i] == 1)
            {
                if (seen[i] && !seen_finish[i]) return true; //閉区間!!
                if (DFS(i, st)) return true;//次へ移動
            }
        }

        seen_finish[st] = true;
        return false;
    }

グラフが連結ではないときの、全グラフの閉区間チェック

DFSはさっきと同じ。
DFSを呼ぶとき、全頂点をループする必要がある。

// 下記のように使用
for (int i = 0; i < N; i++)
{
    if (seen[i]) continue; //別のグラフで確認済みなので飛ばす

    if (DFS(s))
        Console.WriteLine("Yes"); // 閉区間がある
    else
        Console.WriteLine("No");
}

その他

以下はDFSでも解けるが、BFS(幅優先探索)でやるべき問題…？たぶん？

・最短経路を求める問題
・t→sに移動可能な時、その経路全てを返す問題
・(i-1)回目の移動情報が(i)回目の移動に影響を与える問題

これからも経験値つんでいきます。