はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

【C#】幅優先探索(BFS)を実装してみる

はじめに

前回深さ優先探索の実装をしてみました。
www.hanachiru-blog.com

この深さ優先探索と兄弟のようなアルゴリズムである幅優先探索を実装していきたいと思います。

実装方針

実は深さ優先探索ではスタックを用いていましたが、それをキューに変えるだけで幅優先探索が実装できます。

  1. 始点のノードをキューに入れる
  2. キューにノードがあれば取り出し、なければ探索を終了する
  3. 取り出したノードが目的のノードなら終了
  4. 取り出したノードに隣接したノードをキューに積む
  5. 2に戻る

f:id:hanaaaaaachiru:20200518170210p:plain

コード

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

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

    /// <summary>
    /// 初期化
    /// </summary>
    /// <param name="vertices">頂点の集合</param>
    public BreadthFirstSearch(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 BreadthFirstSearch<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 queue = new Queue<T>();
        queue.Enqueue(start);
        _graph[start].IsSeen = true;

        while (queue.Count != 0)
        {
            T state = queue.Dequeue();
            foreach (var v in _graph[state].To)
            {
                if (_graph[v].IsSeen == false)
                {
                    _graph[v].IsSeen = true;
                    queue.Enqueue(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 graph = new BreadthFirstSearch<int>(Enumerable.Range(1, 5));        // {1, 2, 3, 4, 5}

    graph.Add(1, 2)
        .Add(1, 5)
        .Add(2, 3)
        .Add(2, 4);

    Console.WriteLine(graph.IsExist(1, 4));                                 // True
    Console.WriteLine(graph.IsExist(2, 5));                                 // False
}

f:id:hanaaaaaachiru:20200518170210p:plain

また前回と同様にstringなんかもOKです。

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

    graph.Add("北海道", "東京")
        .Add("北海道", "宮城")
        .Add("東京", "大阪")
        .Add("東京", "福岡");

    Console.WriteLine(graph.IsExist("北海道", "福岡"));         // True
    Console.WriteLine(graph.IsExist("東京", "宮城"));           // False
}

f:id:hanaaaaaachiru:20200516130245p:plain

有向グラフであることに注意してください。

さいごに

くどくて申し訳ないですが、内部構造にDictonaryを使っていたりメモを再利用するかの判断でもObject.Equalを使っているので、特に参照型を使う場合は注意してください。
【C#】シーケンスが等しいかどうかを同じ要素なら等しくする - はなちるのマイノート

int,long,stringとかなら全く問題はないです。

良かったらううまく活用してみてください。

ではまた。