C#实现最小生成树的边权值过滤（小白也能学会的图论实战教程）

什么是边权值过滤？

假设你有一个带权无向图，每条边都有一个权重（例如距离、成本、延迟等）。在某些场景下，你可能不希望使用所有边——比如排除掉成本过高的连接。这时就需要对边进行权值过滤。

例如：只保留权重 ≤ 10 的边，然后在这个“过滤后”的子图上构建最小生成树。这就是本文要解决的核心问题。

技术选型：为什么用 Prim 算法？

构建最小生成树有两种主流算法：Kruskal 和 Prim。Kruskal 基于边排序，适合稀疏图；Prim 基于顶点扩展，适合稠密图。由于我们要在原始图上动态过滤边，使用邻接表+Prim 更直观、易于控制。

我们将使用 C# 实现一个灵活的图结构，并在 Prim 算法执行前先过滤掉不符合条件的边。

完整 C# 代码实现

下面是一个完整的、可运行的 C# 控制台程序，包含图的定义、边过滤和 Prim 算法实现：

using System;using System.Collections.Generic;using System.Linq;class Edge{    public int From { get; set; }    public int To { get; set; }    public int Weight { get; set; }    public Edge(int from, int to, int weight)    {        From = from;        To = to;        Weight = weight;    }}class Graph{    private List<Edge> edges;    private int vertexCount;    public Graph(int vertices)    {        vertexCount = vertices;        edges = new List<Edge>();    }    public void AddEdge(int from, int to, int weight)    {        edges.Add(new Edge(from, to, weight));    }    public List<Edge> GetFilteredEdges(int maxWeight)    {        // 过滤：只保留权重不超过 maxWeight 的边        return edges.Where(e => e.Weight <= maxWeight).ToList();    }    public List<Edge> PrimMST(int maxWeight)    {        var filteredEdges = GetFilteredEdges(maxWeight);                // 构建邻接表        var adj = new Dictionary<int, List<(int to, int weight)>>();        for (int i = 0; i < vertexCount; i++)            adj[i] = new List<(int, int)>();        foreach (var edge in filteredEdges)        {            adj[edge.From].Add((edge.To, edge.Weight));            adj[edge.To].Add((edge.From, edge.Weight)); // 无向图        }        // Prim 算法        var inMST = new bool[vertexCount];        var minWeight = new int[vertexCount];        var parent = new int[vertexCount];        for (int i = 0; i < vertexCount; i++)        {            minWeight[i] = int.MaxValue;            parent[i] = -1;        }        minWeight[0] = 0;        var mstEdges = new List<Edge>();        for (int count = 0; count < vertexCount; count++)        {            // 找到不在 MST 中且权重最小的顶点            int u = -1;            for (int v = 0; v < vertexCount; v++)            {                if (!inMST[v] && (u == -1 || minWeight[v] < minWeight[u]))                    u = v;            }            if (u == -1) break; // 图不连通            inMST[u] = true;            if (parent[u] != -1)            {                mstEdges.Add(new Edge(parent[u], u, minWeight[u]));            }            // 更新邻接顶点的最小权重            foreach (var (v, w) in adj[u])            {                if (!inMST[v] && w < minWeight[v])                {                    minWeight[v] = w;                    parent[v] = u;                }            }        }        return mstEdges;    }}class Program{    static void Main()    {        // 创建一个有 5 个顶点的图        var 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);        // 只保留权重 ≤ 6 的边，再求 MST        var mst = graph.PrimMST(maxWeight: 6);        Console.WriteLine("过滤后（权重 ≤ 6）的最小生成树边：");        foreach (var edge in mst)        {            Console.WriteLine($"{edge.From} -- {edge.To} == {edge.Weight}");        }    }}

代码解析

• Edge 类：表示一条带权边，包含起点、终点和权重。
• Graph 类：管理所有边，并提供 GetFilteredEdges 方法实现边权值过滤。
• PrimMST 方法：接收一个 maxWeight 参数，先过滤边，再用 Prim 算法构建 MST。
• 主程序：构造一个简单图，调用 PrimMST(6)，只使用权重 ≤ 6 的边。

运行结果将输出符合条件的最小生成树边集合。如果过滤后图不连通，算法会自动停止（你也可以根据需求抛出异常或返回空列表）。

SEO 关键词回顾

本文围绕以下核心 SEO 关键词展开：

• C#最小生成树：使用 C# 实现 MST 算法。
• 边权值过滤：在构建 MST 前对边进行条件筛选。
• Prim算法：采用 Prim 而非 Kruskal，更适合动态过滤场景。
• C#图论教程：面向初学者的图论编程实践指南。

总结

通过本文，你学会了如何在 C# 中实现一个支持边权值过滤的最小生成树算法。这不仅加深了你对图论的理解，也提升了你在实际项目中处理复杂网络数据的能力。

你可以进一步扩展此代码，比如支持多种过滤条件（如权重范围）、可视化图结构，或改用优先队列优化 Prim 算法性能。

动手试试吧！编程的世界，从理解一个算法开始。