4th term 5th week - dsuz/csharp GitHub Wiki

今回のテーマ

  • グラフ
  • 深さ優先探索 (Depth First Search, DFS)

用語の説明

グラフとは、頂点（ノード）を辺で繋いだもの。Unity のアニメーターコントローラーや Visual Scripting もグラフである。

※vertex の複数形は vertexes ではなく vertices です。

探索とは

例えば、前述のグラフ上で頂点４から頂点３へ移動するルートを求める計算のことを探索という。なお、グラフでは辺に沿って移動可能とし、今回のグラフでは辺は双方向に移動可能とする。

この場合、頂点４から頂点３へ移動するルートは、例えば 4→1→5→3である。

深さ優先探索とは

探索アルゴリズムはいろいろあり、状況や条件によってさまざまなアルゴリズムが使われる。それらのうち、もっとも基本的なものは深さ優先探索 (Depth First Search, DFS) と幅優先探索 (Breadth First Search) である。今回は前者を扱う。

深さ優先探索では、スタックと再起呼び出しを使うことが特徴的である。

基本的な考え方

深さ優先探索は「右手法（左手法）」で探索を行う。例えば次のグラフで頂点０から頂点３に移動したい時、下図のようにして道を探す。

**

これをプログラミングで求めたい時、以下の情報が必要になる。

  1. 頂点数
  2. スタートする頂点
  3. ゴールとなる頂点
  4. 隣接情報

この隣接情報がポイントである。隣接情報（どの頂点とどの頂点がつながっているか）をデータとして保持しておく必要がある。今回は例として隣接行列で保持するが、上のグラフの場合、隣接行列は次のデータになる。

0 1 2 3 4 5 6
0 false true false false false false false
1 true false true false true true false
2 true false false false false true false
3 false false false false false true false
4 false true false false false false false
5 false true true true false false false
6 false false false false false false false

列がある頂点、行が次に移動する頂点とする。例えば、上のグラフでは 0 → 1 にも 1→ 0 にも移動可能なので、[0, 1] と [1, 0] に true を入れている。false は移動できないという意味である。

どうプログラミングするのか

前項で、以下の情報が必要になると述べた。

  1. 頂点数
  2. スタートする頂点
  3. ゴールとなる頂点
  4. 隣接情報

これは、データとしては次のように与えられる。

コピペ用にテキストのデータも示しておく。

6 4 3 6
0 1
1 2
1 4
1 5
2 5
3 5

アルゴリズム（手順）としては次のようになる。

  1. スタックに現在いる頂点をプッシュする
  2. 現在いる頂点を「訪問済み頂点」として覚えておく
  3. 未訪問の隣接頂点を探す
  4. 未訪問の隣接頂点が見つかったら、それを訪問済みにしてスタックにプッシュする これでスタックの一番上にいるノードが「現在いる頂点」になる
  5. 現在いる頂点がゴールだったら、経路が見つかった、ということになる
  6. 見つかった頂点がゴールではない時は、引き続き探索を行う この時、再起呼び出しを使って ３. に戻る
  7. 再起呼び出しから戻ってきたら、頂点を戻る（スタックからポップし、その頂点を未訪問に戻す）
  8. 未訪問の頂点が見つからなくなるまで 3. に戻る

この手順は文章だけで説明するのは難しいので、以下のコード例を参照し、各変数にどのようなデータが格納されるのかを更新しながら絵を描くとよいでしょう。書籍「アルゴリズムとデータ構造」では絵で説明していますが、自分で描かず見るだけで理解するのは無理でしょう。

コード例

再起呼び出し内で一貫して使う変数 route, adj, visitedNodes, nodeCount, goal を引数として渡しているが、これらの変数をフィールドにして、クラスをスコープにしても問題ない。

※引数 route, adj, visitedNodes は ref をつけていないのに、コピーされておらず、メソッド内で変数を更新しているのにメソッドを抜けても更新された内容が維持されている。これは「クラス変数は参照を渡される」からですが、これがどういう事なのか考えてみるとよいでしょう。

using System;
using System.Collections.Generic;   // Stack<> のため
using System.Linq;  // Reverse() のため

class Program
{
    static void Main(string[] args)
    {
        var prms = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int n = prms[0], start = prms[1], goal = prms[2], rowCount = prms[3];    // n: 頂点数, rowCount: 読み込む隣接情報の行数
        var adj = new bool[n, n];  // 隣接 (adjacent) 情報を入れる行列
        var visitedNodes = new bool[n]; // 訪問済み頂点

        for (int i = 0; i < rowCount; i++)
        {
            var edges = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            adj[edges[0], edges[1]] = true;
            adj[edges[1], edges[0]] = true; // 双方向に移動可能なので、0 -> 1 も移動できるし 1 -> 0 も移動できる
        }   // 隣接情報を読み込む

        var route = new Stack<int>();   // 現在進行中のルートを記憶する
        route.Push(start);  // スタート地点を入れる
        visitedNodes[start] = true; // スタート地点は訪問済みにする
        DFS(route, adj, visitedNodes, n, goal); // 探索開始
    }

    /// <summary>
    /// 深さ優先探索を行う
    /// </summary>
    /// <param name="route">現在までのルートが入った Stack</param>
    /// <param name="adj">隣接行列</param>
    /// <param name="visitedNodes">訪問済み頂点</param>
    /// <param name="nodeCount">頂点数</param>
    /// <param name="goal">ゴールとなる頂点</param>
    static void DFS(Stack<int> route, bool[,] adj, bool[] visitedNodes, int nodeCount, int goal)
    {
        var currentNode = route.Pop();  // 今いるノード
        route.Push(currentNode);    //　Peek でもいいけど

        for (int i = 0; i < nodeCount; i++)
        {
            var nextNode = i;   // 移動先頂点

            if (!visitedNodes[nextNode] && adj[currentNode, nextNode])
            {
                route.Push(nextNode);
                visitedNodes[nextNode] = true;

                if (nextNode == goal)
                {
                    Console.WriteLine(string.Join("->", route.Reverse()));
                }   // ゴールに到着した
                else
                {
                    DFS(route, adj, visitedNodes, nodeCount, goal);
                }   // ゴールじゃなかったら引き続き探索する

                visitedNodes[route.Pop()] = false;  // 探索が終わったので、戻る
            }   // 移動先に移動可能、かつ未訪問ならそこに移動する
        }
    }
}

深さ優先探索の特徴

以下の特徴は必ず抑えておきましょう。

  1. 右手法（左手法）をアルゴリズム化したものである
  2. 再起呼び出しとスタックを使う
  3. 最初に見つかった経路が最短とは限らない

深さ優先探索を使う問題

以下の問題を解いてみましょう。

  1. グラフの s,t パス
  2. グラフの s,t パス 2

Unity のサンプル

https://github.com/dsuz/algorithm-data-structure-examples

⚠️ **GitHub.com Fallback** ⚠️