当前位置：首页 > C# > 正文

C#实现最小生成树权值计算（从零开始掌握图论核心算法）

主机测评网
C#
2025-12-14
574

在计算机科学中，最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题。它广泛应用于网络设计、电路布线、聚类分析等领域。本文将手把手教你如何使用C#语言实现最小生成树的权值计算，即使你是编程小白，也能轻松理解并上手！

什么是“最小生成树”？

假设你有一个带权无向连通图（即图中任意两点之间都有路径，且边有权重），最小生成树就是这个图的一个子图，它满足以下条件：

包含图中所有的顶点；
是一棵树（无环、连通）；
所有边的权值之和最小。

C#实现最小生成树权值计算（从零开始掌握图论核心算法） C#最小生成树最小生成树权值计算 C#图算法 Prim算法C#实现第1张

常用算法：Prim 算法简介

计算最小生成树的经典算法有两个：Prim 算法和 Kruskal 算法。本文我们将使用 Prim 算法，因为它非常适合用邻接矩阵表示的稠密图，并且逻辑清晰，易于理解。

Prim 算法的基本思想是：从一个起始顶点出发，每次选择连接已选顶点集合与未选顶点集合的最小权值边，逐步扩展生成树，直到包含所有顶点。

C# 实现最小生成树权值计算

下面我们用 C# 编写一个完整的程序，使用 Prim 算法计算最小生成树的总权值。

using System;public class MinimumSpanningTree{    private static readonly int INF = int.MaxValue;    // 使用 Prim 算法计算最小生成树的总权值    public static int PrimMST(int[,] graph, int vertices)    {        int[] key = new int[vertices];      // 存储每个顶点到 MST 的最小边权        bool[] inMST = new bool[vertices];  // 标记顶点是否已在 MST 中        int totalWeight = 0;        // 初始化 key 数组为无穷大        for (int i = 0; i < vertices; i++)        {            key[i] = INF;            inMST[i] = false;        }        // 从顶点 0 开始        key[0] = 0;        for (int count = 0; count < vertices; count++)        {            // 找到 key 最小且不在 MST 中的顶点            int u = -1;            for (int v = 0; v < vertices; v++)            {                if (!inMST[v] && (u == -1 || key[v] < key[u]))                    u = v;            }            // 将 u 加入 MST            inMST[u] = true;            totalWeight += key[u];            // 更新 u 的所有邻接顶点的 key 值            for (int v = 0; v < vertices; v++)            {                if (graph[u, v] != 0 && !inMST[v] && graph[u, v] < key[v])                {                    key[v] = graph[u, v];                }            }        }        return totalWeight;    }    // 测试示例    public static void Main()    {        // 示例图（邻接矩阵表示）        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;        int mstWeight = PrimMST(graph, vertices);        Console.WriteLine($"最小生成树的总权值为: {mstWeight}");        // 输出: 最小生成树的总权值为: 16    }}