【C#】深さ優先探索(DFS)を実装してみる

はじめに

今回は深さ優先探索を実装してみようという記事になります！

深さ優先探索とはこちら。

木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。

深さ優先探索 - Wikipedia

幅優先探索(BFS)と似たアルゴリズムですが、計算量は幅優先探索の空間計算量より最悪のケースでは同じだけれど一般的なケースではずっと小さいそうです。

計算量は　グラフ $G = (V, E)$ 　(頂点がV個，辺がE個)　において $o(V+E)$ です。

早速詳しくみていきましょう。

はじめに
実装方針
コード
使い方
さいごに

実装方針

スタックを用いた方法と再帰関数を用いた方法がありますが、今回はスタックを用いた方法を選択します。

流れはこんな感じ。

始点のノードをスタックに入れる
スタックにノードがあれば取り出し、なければ探索を終了する
取り出したノードが目的のノードなら終了
取り出したノードに隣接したノードをスタックに積む
２に戻る

f:id:hanaaaaaachiru:20200516115101p:plain

コード

public class DepthFirstSerch<T>
{
    private Dictionary<T, Node> _graph;

    private Dictionary<T, bool> _memo;
    private T _memoStart;

    /// <summary>
    /// 初期化
    /// </summary>
    /// <param name="vertices">頂点の集合</param>
    public DepthFirstSerch(IEnumerable<T> vertices)
    {
        _graph = new Dictionary<T, Node>();
        _memo = new Dictionary<T, bool>();
        _memoStart = default(T);
        foreach (var v in vertices)
            _graph[v] = new Node();
    }

    /// <summary>
    /// グラフに辺を追加する
    /// </summary>
    /// <param name="from">接続元</param>
    /// <param name="to">接続先</param>
    public DepthFirstSerch<T> Add(T from, T to)
    {
        _memo = new Dictionary<T, bool>();
        _memoStart = default(T);
        _graph[from].Add(to);
        return this;
    }

    /// <summary>
    /// 要素が存在するかどうか
    /// </summary>
    /// <param name="start">始点</param>
    /// <param name="target">探す要素</param>
    /// <returns></returns>
    public bool IsExist(T start, T target)
    {
        // 条件が異なっていなければメモしておいたものを返す
        if (Equals(_memoStart, start) && _memo.ContainsKey(target)) return _memo[target];

        foreach (var node in _graph) node.Value.IsSeen = false;
        var stack = new Stack<T>();
        stack.Push(start);
        _graph[start].IsSeen = true;

        while (stack.Count != 0)
        {
            T state = stack.Pop();
            foreach (var v in _graph[state].To)
            {
                if (_graph[v].IsSeen == false)
                {
                    _graph[v].IsSeen = true;
                    stack.Push(v);
                }
            }
        }

        _memo = _graph.ToDictionary(graph => graph.Key, graph => graph.Value.IsSeen);
        _memoStart = start;

        return _graph[target].IsSeen;
    }

    public class Node
    {
        public List<T> To { get; private set; }
        public bool IsSeen { get; set; }

        public Node()
        {
            To = new List<T>();
            IsSeen = false;
        }

        public void Add(T item)
            => To.Add(item);
    }
}

使い方

static void Main(string[] args)
{
    var vertices = Enumerable.Range(1, 5);         // {1,2,3,4,5}
    var dfs = new DepthFirstSerch<int>(vertices);

    // 辺を追加する
    dfs.Add(1, 2)
        .Add(1, 5)
        .Add(2, 3)
        .Add(2, 4);

    // 番号1から探索を開始し、番号4のノードが存在するか
    Console.WriteLine(dfs.IsExist(1, 4));          // True
    Console.WriteLine(dfs.IsExist(2, 5));          // False
}

f:id:hanaaaaaachiru:20200516115101p:plain

図では無向グラフっぽくなっていなすが、内部的には有向グラフになっていることに注意してください。

またノードのラベルは数字だけではなくジェネリックにしておいたので、こんなことも可能です。

static void Main(string[] args)
{
    var vertices = new string[] { "北海道", "東京", "宮城", "大阪", "福岡" };
    var dfs = new DepthFirstSerch<string>(vertices);

    // 辺を追加する
    dfs.Add("北海道", "東京")
        .Add("北海道", "宮城")
        .Add("東京", "大阪")
        .Add("東京", "福岡");

    // 北海道から探索を開始し、福岡のノードが存在するか
    if (dfs.IsExist("北海道", "福岡")) Console.WriteLine("Yes");
}