【C#】幅優先探索(BFS)を実装してみる - はなちるのマイノート

はじめに

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

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

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

実装方針

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

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

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
}