8-14 最小全域木問題

問題

最小全域木を求める。

問題


答え

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct GraphInfoDef
    {
        internal char FromPos;
        internal char ToPos;
        internal int Cost;
    }

    static void Main()
    {
        GraphInfoDef[] GraphArr = new GraphInfoDef[9];
        GraphArr[0].FromPos = 'A'; GraphArr[0].ToPos = 'B'; GraphArr[0].Cost = 5;
        GraphArr[1].FromPos = 'A'; GraphArr[1].ToPos = 'C'; GraphArr[1].Cost = 2;
        GraphArr[2].FromPos = 'B'; GraphArr[2].ToPos = 'C'; GraphArr[2].Cost = 4;
        GraphArr[3].FromPos = 'B'; GraphArr[3].ToPos = 'D'; GraphArr[3].Cost = 2;
        GraphArr[4].FromPos = 'C'; GraphArr[4].ToPos = 'D'; GraphArr[4].Cost = 3;
        GraphArr[5].FromPos = 'C'; GraphArr[5].ToPos = 'E'; GraphArr[5].Cost = 2;
        GraphArr[6].FromPos = 'D'; GraphArr[6].ToPos = 'E'; GraphArr[6].Cost = 6;
        GraphArr[7].FromPos = 'D'; GraphArr[7].ToPos = 'F'; GraphArr[7].Cost = 6;
        GraphArr[8].FromPos = 'E'; GraphArr[8].ToPos = 'F'; GraphArr[8].Cost = 4;

        //プリム法で最小全域木を求める
        var PriorityQueue = new CppPriorityQueue();

        //到達済ノードのSet
        var ToutatuNodeSet = new HashSet<char>();

        //Enqueue処理
        Action<char> EnqueueAct = pConnNode =>
        {
            ToutatuNodeSet.Add(pConnNode);
            foreach (GraphInfoDef EachGraphInfo in GraphArr) {
                if (EachGraphInfo.FromPos == pConnNode) {
                    //到達済ノードならContinue
                    if (ToutatuNodeSet.Contains(EachGraphInfo.ToPos)) continue;

                    PriorityQueue.Enqueue(EachGraphInfo.ToPos, EachGraphInfo.Cost);
                }
                if (EachGraphInfo.ToPos == pConnNode) {
                    //到達済ノードならContinue
                    if (ToutatuNodeSet.Contains(EachGraphInfo.FromPos)) continue;

                    PriorityQueue.Enqueue(EachGraphInfo.FromPos, EachGraphInfo.Cost);
                }
            }
        };
        EnqueueAct('A');
        int SumCost = 0;

        while (PriorityQueue.Count > 0) {
            PriorityQueueItemDef Dequeued = PriorityQueue.Dequeue();

            //到達済ノードならContinue
            if (ToutatuNodeSet.Contains(Dequeued.ToNode)) continue;

            SumCost += Dequeued.EdaCost;
            EnqueueAct(Dequeued.ToNode);

            Console.WriteLine("{0}への枝を追加。コスト={1}", Dequeued.ToNode, Dequeued.EdaCost);
        }
        Console.WriteLine("最小全域木のコスト合計={0}", SumCost);
    }
}

//PriorityQueueもどき
struct PriorityQueueItemDef
{
    internal char ToNode;
    internal int EdaCost;
}
class CppPriorityQueue
{
    private List<PriorityQueueItemDef> mItemList = new List<PriorityQueueItemDef>();

    internal int Count { get { return mItemList.Count; } }

    internal void Enqueue(char pToNode, int pEdaCost)
    {
        mItemList.Add(new PriorityQueueItemDef() { ToNode = pToNode, EdaCost = pEdaCost });
    }

    internal PriorityQueueItemDef Dequeue()
    {
        int wkInd = 0;
        for (int I = 1; I <= mItemList.Count - 1; I++) {
            //コストが最小の枝を返す
            if (mItemList[I].EdaCost < mItemList[wkInd].EdaCost)
                wkInd = I;
        }
        PriorityQueueItemDef WillRetun = mItemList[wkInd];
        mItemList.RemoveAt(wkInd);
        return WillRetun;
    }
}

実行結果

Cへの枝を追加。コスト=2
Eへの枝を追加。コスト=2
Dへの枝を追加。コスト=3
Bへの枝を追加。コスト=2
Fへの枝を追加。コスト=4
最小全域木のコスト合計=13

解説

プリム法のアリゴリズムを使ってます。