Prim算法详解（C#语言实现最小生成树的完整教程）

C# 实现 Prim 算法

下面我们用 C# 编写一个完整的 Prim 算法程序。为了便于理解，我们将使用邻接矩阵来表示图。

步骤说明：

1. 定义图的结构（使用二维数组表示邻接矩阵）；
2. 维护两个数组：key[] 存储每个顶点到生成树的最小边权重，mstSet[] 标记顶点是否已加入生成树；
3. 初始化：起点 key 为 0，其余为无穷大；
4. 循环 V-1 次（V 为顶点数），每次选取 key 最小且未加入 MST 的顶点，更新其邻居的 key 值。

完整代码示例：

using System;class PrimAlgorithm{    private static readonly int INF = int.MaxValue;    // 打印最小生成树的结果    static void PrintMST(int[] parent, int[,] graph, int vertices)    {        Console.WriteLine("边 \t\t 权重");        for (int i = 1; i < vertices; i++)        {            Console.WriteLine($"{parent[i]} - {i} \t\t {graph[i, parent[i]]}");        }    }    // 获取 key 最小且未加入 MST 的顶点    static int MinKey(int[] key, bool[] mstSet, int vertices)    {        int min = INF, minIndex = -1;        for (int v = 0; v < vertices; v++)        {            if (!mstSet[v] && key[v] < min)            {                min = key[v];                minIndex = v;            }        }        return minIndex;    }    // Prim 算法主函数    static void PrimMST(int[,] graph, int vertices)    {        int[] parent = new int[vertices];   // 存储 MST 的父节点        int[] key = new int[vertices];      // 存储最小权重        bool[] mstSet = new bool[vertices]; // 是否已加入 MST        // 初始化        for (int i = 0; i < vertices; i++)        {            key[i] = INF;            mstSet[i] = false;        }        key[0] = 0;         // 起始顶点        parent[0] = -1;     // 起始顶点无父节点        for (int count = 0; count < vertices - 1; count++)        {            int u = MinKey(key, mstSet, vertices);            mstSet[u] = true;            // 更新相邻顶点的 key 值            for (int v = 0; v < vertices; v++)            {                if (graph[u, v] != 0 && !mstSet[v] && graph[u, v] < key[v])                {                    parent[v] = u;                    key[v] = graph[u, v];                }            }        }        PrintMST(parent, graph, vertices);    }    // 主函数测试    static void Main(string[] args)    {        /* 示例图（邻接矩阵）           0    1    2    3    4        0 [0,   2,   0,   6,   0]        1 [2,   0,   3,   8,   5]        2 [0,   3,   0,   0,   7]        3 [6,   8,   0,   0,   9]        4 [0,   5,   7,   9,   0]        */        int[,] graph = {            {0, 2, 0, 6, 0},            {2, 0, 3, 8, 5},            {0, 3, 0, 0, 7},            {6, 8, 0, 0, 9},            {0, 5, 7, 9, 0}        };        int vertices = 5;        PrimMST(graph, vertices);    }}

代码解析

上述代码实现了完整的 Prim算法。其中：

• MinKey 函数用于找出尚未加入 MST 且 key 值最小的顶点；
• PrimMST 是核心函数，通过循环逐步构建最小生成树；
• 我们使用邻接矩阵 graph 表示图，0 表示两点之间无边；
• 最终输出每条 MST 边及其权重。

总结

通过本教程，你已经掌握了如何用 C# 实现 Prim算法来求解最小生成树。该算法的时间复杂度为 O(V²)，适用于稠密图。如果你处理的是稀疏图，可以考虑结合优先队列（如堆）优化至 O(E log V)。

掌握 图论算法 对于提升编程能力至关重要，而 C#实现最小生成树 是学习高级算法的良好起点。希望这篇教程对你有所帮助！