C# を使用して最小スパニング ツリー アルゴリズムを作成する方法

C# を使用して最小スパニング ツリー アルゴリズムを作成する方法

最小スパニング ツリー アルゴリズムは、グラフ理論の重要なアルゴリズムであり、次の接続性の問題を解決するために使用されます。グラフ。コンピューター サイエンスでは、最小スパニング ツリーとは、スパニング ツリーのすべてのエッジの重みの合計が最小となる、接続されたグラフのスパニング ツリーを指します。

この記事では、C# を使用して最小のスパニング ツリー アルゴリズムを作成する方法を紹介し、具体的なコード例を示します。

まず、問題を表すグラフ データ構造を定義する必要があります。 C# では、隣接行列を使用してグラフを表現できます。隣接行列は、各要素が 2 つの頂点間のエッジの重みを表す 2 次元配列です。 2 つの頂点間にエッジがない場合は、この値を無限などの特定の値に設定できます。

次は、隣接行列を使用してグラフを表すサンプル コードです:

class Graph
{
    private int[,] matrix;  // 邻接矩阵
    private int numVertices; // 顶点数量

    public Graph(int numVertices)
    {
        this.numVertices = numVertices;
        matrix = new int[numVertices, numVertices];
    }

    public void AddEdge(int startVertex, int endVertex, int weight)
    {
        matrix[startVertex, endVertex] = weight;
        matrix[endVertex, startVertex] = weight;
    }

    public int GetEdge(int startVertex, int endVertex)
    {
        return matrix[startVertex, endVertex];
    }
}

次に、最小の合計重みを持つスパニング ツリーを見つけるために最小スパニング ツリー アルゴリズムを実装する必要があります。 。その中で、Prim アルゴリズムと Kruskal アルゴリズムは、一般的に使用される 2 つの最小スパニング ツリー アルゴリズムです。この記事では、Prim のアルゴリズムを紹介します。

Prim のアルゴリズムの基本的な考え方は、任意の頂点から開始し、現在のスパニング ツリーに接続されているエッジの中から最も重みの小さいエッジを連続的に選択し、このエッジをスパニング ツリーに接続することです。すべての頂点がスパニング ツリーに参加するまで、このプロセスを繰り返します。

以下は、Prim のアルゴリズムを使用して最小スパニング ツリーを実装するコード例です。

class PrimMST
{
    private Graph graph;
    private int[] key;         // 存储对应顶点的权值
    private bool[] mstSet;     // 存储对应顶点是否已加入生成树

    public PrimMST(Graph graph)
    {
        this.graph = graph;
        int numVertices = graph.GetNumVertices();
        key = new int[numVertices];
        mstSet = new bool[numVertices];
    }

    private int MinKey()
    {
        int min = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < graph.GetNumVertices(); v++)
        {
            if (mstSet[v] == false && key[v] < min)
            {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    public void CalculateMST(int startVertex)
    {
        for (int v = 0; v < graph.GetNumVertices(); v++)
        {
            key[v] = int.MaxValue;
            mstSet[v] = false;
        }

        key[startVertex] = 0;

        for (int count = 0; count < graph.GetNumVertices() - 1; count++)
        {
            int u = MinKey();

            if (u == -1)
            {
                break;
            }

            mstSet[u] = true;

            for (int v = 0; v < graph.GetNumVertices(); v++)
            {
                int weight = graph.GetEdge(u, v);

                if (weight > 0 && mstSet[v] == false && weight < key[v])
                {
                    key[v] = weight;
                }
            }
        }

        PrintMST();
    }

    private void PrintMST()
    {
        Console.WriteLine("Edge     Weight");
        for (int v = 1; v < graph.GetNumVertices(); v++)
        {
            Console.WriteLine($"{v} - {key[v]}");
        }
    }
}

最後に、プログラムのエントリ ポイントで、これらのクラスを使用してテストするコードを作成する必要があります。

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(5);
        graph.AddEdge(0, 1, 2);
        graph.AddEdge(0, 3, 6);
        graph.AddEdge(1, 2, 3);
        graph.AddEdge(1, 3, 8);
        graph.AddEdge(1, 4, 5);
        graph.AddEdge(2, 4, 7);
        graph.AddEdge(3, 4, 9);

        PrimMST mst = new PrimMST(graph);
        mst.CalculateMST(0);
    }
}

上記のコードを実行すると、最小スパニングツリーのエッジと重みが出力されます。

上記は、C# を使用して最小スパニング ツリー アルゴリズムを作成する手順とサンプル コードです。アルゴリズムの背後にある原理を理解し、実際のニーズに応じて適切な調整を行うことで、アルゴリズムをより適切に使用して、実際のアプリケーションで対応する問題を解決できます。

以上がC# を使用して最小スパニング ツリー アルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。