Prim算法详解（C#实现最小生成树的高效优化指南）

什么是Prim算法？

Prim算法是一种贪心算法，用于在加权无向连通图中找到一棵包含所有顶点且总权重最小的生成树。其基本思想是：

• 从任意一个顶点开始构建生成树。
• 每次选择连接当前生成树与非树顶点之间权重最小的边。
• 重复上述步骤，直到所有顶点都被包含。

基础版Prim算法（邻接矩阵实现）

首先，我们来看一个使用邻接矩阵的简单实现。假设图有 n 个顶点，我们用一个 n×n 的二维数组存储边的权重。

using System;public class PrimAlgorithm{    private static readonly int INF = int.MaxValue;    public static void Prim(int[,] graph, int vertices)    {        int[] parent = new int[vertices];     // 存储MST的父节点        int[] key = new int[vertices];        // 当前最小边权重        bool[] inMST = new bool[vertices];    // 是否已加入MST        // 初始化        for (int i = 0; i < vertices; i++)        {            key[i] = INF;            inMST[i] = false;        }        key[0] = 0;          // 从顶点0开始        parent[0] = -1;      // 根节点无父节点        for (int count = 0; count < vertices - 1; count++)        {            // 找到key最小且未加入MST的顶点            int u = MinKey(key, inMST, vertices);            inMST[u] = true;            // 更新相邻顶点的key值            for (int v = 0; v < vertices; v++)            {                if (graph[u, v] != 0 && !inMST[v] && graph[u, v] < key[v])                {                    parent[v] = u;                    key[v] = graph[u, v];                }            }        }        PrintMST(parent, graph, vertices);    }    private static int MinKey(int[] key, bool[] inMST, int vertices)    {        int min = INF, minIndex = -1;        for (int v = 0; v < vertices; v++)        {            if (!inMST[v] && key[v] < min)            {                min = key[v];                minIndex = v;            }        }        return minIndex;    }    private static void PrintMST(int[] parent, int[,] graph, int vertices)    {        Console.WriteLine("Edge \tWeight");        for (int i = 1; i < vertices; i++)        {            Console.WriteLine($"{parent[i]} - {i} \t{graph[i, parent[i]]}");        }    }}

这个基础版本的时间复杂度为 O(V²)，其中 V 是顶点数。对于稠密图（边很多）来说效率尚可，但对于稀疏图（边较少）则不够高效。

优化版Prim算法：使用优先队列（最小堆）

为了提升性能，我们可以使用 优先队列（Priority Queue）来快速获取最小权重边。在 C# 中，可以借助 SortedSet 或第三方库（如 System.Collections.Generic.PriorityQueue，.NET 6+ 原生支持）实现最小堆。

优化后的算法时间复杂度可降至 O(E log V)，其中 E 是边数。这对于大规模稀疏图非常关键，也是 图论算法优化 的核心技巧之一。

using System;using System.Collections.Generic;public class OptimizedPrim{    public class Edge : IComparable    {        public int Vertex;        public int Weight;        public Edge(int v, int w)        {            Vertex = v;            Weight = w;        }        public int CompareTo(Edge other)        {            return Weight.CompareTo(other.Weight);        }    }    public static void PrimOptimized(Dictionary> adjList, int start, int vertices)    {        var pq = new SortedSet();        var inMST = new bool[vertices];        var key = new int[vertices];        for (int i = 0; i < vertices; i++) key[i] = int.MaxValue;        key[start] = 0;        pq.Add(new Edge(start, 0));        while (pq.Count > 0)        {            var current = pq.Min;            pq.Remove(current);            int u = current.Vertex;            if (inMST[u]) continue; // 跳过已处理节点            inMST[u] = true;            foreach (var (v, w) in adjList[u])            {                if (!inMST[v] && w < key[v])                {                    key[v] = w;                    pq.Add(new Edge(v, w));                }            }        }        // 输出总权重（可根据需要扩展输出具体边）        long totalWeight = 0;        for (int i = 0; i < vertices; i++)            if (key[i] != int.MaxValue) totalWeight += key[i];        Console.WriteLine($"最小生成树总权重: {totalWeight}");    }}

如何选择实现方式？

- 如果你的图是稠密图（边数接近 V²），使用邻接矩阵 + 基础Prim即可。

- 如果是稀疏图（边数远小于 V²），强烈推荐使用邻接表 + 优先队列的优化版本。

总结

通过本文，你已经掌握了 Prim算法 的基本原理、C# 实现及其优化方法。无论是学习 最小生成树 还是实践 C#实现 图算法，这都是一个重要的里程碑。记住，理解算法背后的逻辑比死记代码更重要！

如果你正在准备面试或研究 图论算法优化，不妨动手实现这两种版本，并测试不同规模的图数据，观察性能差异。实践出真知！

提示：在 .NET 6 及以上版本中，可直接使用 PriorityQueue<TElement, TPriority> 类进一步简化代码。