How to write the minimum spanning tree algorithm using C#

How to use C# to write the minimum spanning tree algorithm

The minimum spanning tree algorithm is an important graph theory algorithm, which is used to solve the connectivity problem of graphs. In computer science, a minimum spanning tree refers to a spanning tree of a connected graph in which the sum of the weights of all edges of the spanning tree is the smallest.

This article will introduce how to use C# to write the minimum spanning tree algorithm and provide specific code examples.

First, we need to define a graph data structure to represent the problem. In C#, you can use an adjacency matrix to represent a graph. An adjacency matrix is ​​a two-dimensional array in which each element represents the weight of an edge between two vertices. If there is no edge between two vertices, this value can be set to a specific identity, such as infinity.

The following is a sample code that uses an adjacency matrix to represent a graph:

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

Next, we need to implement a minimum spanning tree algorithm to find the spanning tree with the minimum total weight. Among them, Prim and Kruskal algorithms are two commonly used minimum spanning tree algorithms. In this article, we will introduce Prim's algorithm.

The basic idea of ​​Prim's algorithm is to start from any vertex, continuously select the edge with the smallest weight among the edges connected to the current spanning tree, and connect this edge to the spanning tree. Repeat this process until all vertices have joined the spanning tree.

The following is a code example that uses Prim's algorithm to implement a minimum spanning tree:

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

Finally, we need to write code at the program entry point to use these classes and test them.

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

Run the above code and the edges and weights of the minimum spanning tree will be output.

The above are the steps and sample code for writing the minimum spanning tree algorithm using C#. By understanding the principles behind the algorithm and making appropriate adjustments according to actual needs, you can better use the algorithm to solve corresponding problems in practical applications.

The above is the detailed content of How to write the minimum spanning tree algorithm using C#. For more information, please follow other related articles on the PHP Chinese website!