Kruskal算法详解（并查集在C#中的实战应用）

为什么需要并查集？

判断“加入某条边是否会形成环”是 Kruskal 算法的关键。而并查集正是解决这类“动态连通性”问题的利器。它可以高效地完成两个操作：

• Find(x)：查找元素 x 所在集合的代表（根节点）
• Union(x, y)：合并 x 和 y 所在的集合

通过这两个操作，我们能快速判断两个顶点是否已经连通——如果它们的根相同，说明已连通，加边会成环；否则可以安全添加。

C# 实现并查集

首先，我们用 C# 编写一个简单的并查集类：

public class UnionFind{    private int[] parent;    private int[] rank; // 用于优化合并操作    public UnionFind(int n)    {        parent = new int[n];        rank = new int[n];        for (int i = 0; i < n; i++)        {            parent[i] = i; // 初始时每个节点是自己的父节点            rank[i] = 0;        }    }    // 查找根节点（带路径压缩）    public int Find(int x)    {        if (parent[x] != x)        {            parent[x] = Find(parent[x]); // 路径压缩        }        return parent[x];    }    // 合并两个集合（按秩合并）    public void Union(int x, int y)    {        int rootX = Find(x);        int rootY = Find(y);        if (rootX != rootY)        {            // 按秩合并，保持树尽量平衡            if (rank[rootX] < rank[rootY])            {                parent[rootX] = rootY;            }            else if (rank[rootX] > rank[rootY])            {                parent[rootY] = rootX;            }            else            {                parent[rootY] = rootX;                rank[rootX]++;            }        }    }}  

C# 实现 Kruskal 算法

接下来，我们定义图的边结构，并实现完整的 Kruskal 算法：

using System;using System.Collections.Generic;using System.Linq;// 定义边public class Edge{    public int Source { get; set; }    public int Destination { get; set; }    public int Weight { get; set; }    public Edge(int s, int d, int w)    {        Source = s;        Destination = d;        Weight = w;    }}public class KruskalAlgorithm{    public static List<Edge> FindMST(int vertexCount, List<Edge> edges)    {        // 按权重升序排序        var sortedEdges = edges.OrderBy(e => e.Weight).ToList();        var mst = new List<Edge>();        var uf = new UnionFind(vertexCount);        foreach (var edge in sortedEdges)        {            // 如果两个顶点不在同一集合中            if (uf.Find(edge.Source) != uf.Find(edge.Destination))            {                mst.Add(edge);                uf.Union(edge.Source, edge.Destination);                // MST 有 V-1 条边即可停止                if (mst.Count == vertexCount - 1)                    break;            }        }        return mst;    }}  

完整使用示例

class Program{    static void Main()    {        int vertices = 4;        var edges = new List<Edge>        {            new Edge(0, 1, 10),            new Edge(0, 2, 6),            new Edge(0, 3, 5),            new Edge(1, 3, 15),            new Edge(2, 3, 4)        };        var mst = KruskalAlgorithm.FindMST(vertices, edges);        Console.WriteLine("最小生成树的边：");        int totalWeight = 0;        foreach (var edge in mst)        {            Console.WriteLine($"{edge.Source} -- {edge.Destination} == {edge.Weight}");            totalWeight += edge.Weight;        }        Console.WriteLine($"总权重: {totalWeight}");    }}  

运行结果将输出最小生成树的边及其总权重。这个例子展示了如何用 C# 结合Kruskal算法和并查集高效求解最小生成树问题。

总结

Kruskal 算法因其简洁性和高效性，在图论中占有重要地位。而并查集作为其核心支撑数据结构，通过路径压缩和按秩合并，使得算法整体时间复杂度接近 O(E log E)，非常适合处理大规模稀疏图。无论你是学习C#图论算法，还是准备面试，掌握这一组合都是必备技能。

希望这篇教程能帮助你轻松理解 Kruskal 算法与并查集的配合机制！