【C#】木の直径を求める - はなちるのマイノート

はじめに

今回は木の直径を求めてみようという記事になります！

あまり用いる機会はないと思いますが、簡単な頭の体操のように捉えてくれれば嬉しいです。

早速みていきましょう。

はじめに
木の直径とは？
実装方針
コード
さいごに

木の直径とは？

木の直径とは木の最遠頂点間の距離を指します。

例えばこんな感じ。

f:id:hanaaaaaachiru:20200518220812p:plain

この場合の木の直径は5になります。

ちなみに木は連結で閉路を持たない(無向)グラフのことを指すので、無限ループのようなことは起こらないです。
ja.wikipedia.org

実装方針

適当な頂点sから深さ優先探索を用いて最も遠い頂点uを求める
頂点uから最も遠い頂点vを求める
(u, v) は最遠頂点対

証明はこちらのサイトで解説されていました。
Spaghetti Source - 木の直径

コード

以前実装した深さ優先探索を改造して、コストを取得できるようにしました。
【C#】深さ優先探索(DFS)を実装してみる - はなちるのマイノート

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

    /// <summary>
    /// 初期化
    /// </summary>
    /// <param name="vertices">頂点の集合</param>
    public BreadthFirstSearch(IEnumerable<T> vertices)
    {
        _graph = new Dictionary<T, Node>();
        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)
    {
        _graph[from].Add(to);
        return this;
    }

    /// <summary>
    /// コストを取得する
    /// </summary>
    /// <param name="start">始点</param>
    /// <returns>コスト</returns>
    public Dictionary<T, long> GetCosts(T start)
    {
        var costs = new Dictionary<T, long>();
        foreach (var node in _graph) node.Value.IsSeen = false;
        var queue = new Queue<T>();
        queue.Enqueue(start);
        _graph[start].IsSeen = true;
        costs[start] = 0;

        while (queue.Count != 0)
        {
            T state = queue.Dequeue();
            foreach (var v in _graph[state].To)
            {
                if (_graph[v].IsSeen == false)
                {
                    _graph[v].IsSeen = true;
                    costs[v] = costs[state] + 1;
                    queue.Enqueue(v);
                }
            }
        }

        return costs;
    }

    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(0, 8));

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

    // s(=0)から深さ優先探索をし、uを求める
    var s = 0;
    var costs = graph.GetCosts(s);
    var u = costs.OrderByDescending(t => t.Value)
        .First();

    // uから深さ優先探索をし、vを求める (u, v)が求めるペア
    costs = graph.GetCosts(u.Key);
    var v = costs.OrderByDescending(t => t.Value)
        .First();

    // uからvまでのコストが格納されている
    Console.WriteLine(v.Value);
}