Bagaimana untuk menulis algoritma pokok rentang minimum menggunakan C#

Cara menulis algoritma pokok rentang minimum menggunakan C#

Algoritma pokok rentang minimum ialah algoritma teori graf yang penting, yang digunakan untuk menyelesaikan masalah ketersambungan graf. Dalam sains komputer, pokok rentang minimum merujuk kepada pokok rentang bagi graf bersambung di mana jumlah pemberat semua tepi pokok rentang adalah yang terkecil.

Artikel ini akan memperkenalkan cara menggunakan C# untuk menulis algoritma pepohon rentang minimum dan memberikan contoh kod khusus.

Pertama, kita perlu mentakrifkan struktur data graf untuk mewakili masalah. Dalam C#, anda boleh menggunakan matriks bersebelahan untuk mewakili graf. Matriks bersebelahan ialah tatasusunan dua dimensi di mana setiap elemen mewakili berat tepi antara dua bucu. Jika tiada tepi antara dua bucu, nilai ini boleh ditetapkan kepada pengecam tertentu, seperti infiniti.

Berikut ialah kod sampel yang menggunakan matriks bersebelahan untuk mewakili graf:

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];
    }
}

Seterusnya, kita perlu melaksanakan algoritma pokok rentang minimum untuk mencari pokok rentang dengan jumlah berat minimum. Antaranya, algoritma Prim dan Kruskal adalah dua algoritma pokok rentang minimum yang biasa digunakan. Dalam artikel ini, kami akan memperkenalkan algoritma Prim.

Idea asas algoritma Prim ialah bermula dari mana-mana bucu, terus pilih tepi dengan berat terkecil antara tepi yang disambungkan ke pokok rentang semasa, dan sambungkan tepi ini ke pokok rentang. Ulangi proses ini sehingga semua bucu telah bergabung dengan pokok rentang.

Berikut ialah contoh kod untuk melaksanakan pepohon rentang minimum menggunakan algoritma 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]}");
        }
    }
}

Akhir sekali, kita perlu menulis kod untuk menggunakan kelas ini pada titik masuk program dan mengujinya.

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);
    }
}

Jalankan kod di atas dan tepi dan berat pokok rentang minimum akan dikeluarkan.

Di atas adalah langkah dan kod contoh untuk menulis algoritma pepohon rentang minimum menggunakan C#. Dengan memahami prinsip di sebalik algoritma dan membuat pelarasan yang sesuai mengikut keperluan sebenar, anda boleh menggunakan algoritma dengan lebih baik untuk menyelesaikan masalah yang sepadan dalam aplikasi praktikal.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma pokok rentang minimum menggunakan C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!