CShap Kruskal 源代码

下面是C#语言实现Kruskal算法的源代码：

using System;
using System.Collections.Generic;

public class Graph
{
    private int V, E; // 顶点数和边数
    private List<Edge> edges; // 存储边的列表

    public Graph(int V, int E)
    {
        this.V = V;
        this.E = E;
        edges = new List<Edge>();
    }

    // 添加一条边到图中
    public void AddEdge(int u, int v, int w)
    {
        edges.Add(new Edge(u, v, w));
    }

    // 查找节点所属的集合
    private int Find(int[] parent, int i)
    {
        if (parent[i] == -1)
            return i;
        return Find(parent, parent[i]);
    }

    // 合并两个集合
    private void Union(int[] parent, int x, int y)
    {
        int xset = Find(parent, x);
        int yset = Find(parent, y);
        parent[xset] = yset;
    }

    // 执行Kruskal算法
    public void KruskalMST()
    {
        List<Edge> result = new List<Edge>();

        // 按权值从小到大排序
        edges.Sort();

        int[] parent = new int[V];
        for (int i = 0; i < V; i++)
            parent[i] = -1;

        int i = 0;
        while (result.Count < V - 1 && i < E)
        {
            Edge next_edge = edges[i++];

            int x = Find(parent, next_edge.u);
            int y = Find(parent, next_edge.v);

            // 如果加入这条边不会形成环，则加入到结果中
            if (x != y)
            {
                result.Add(next_edge);
                Union(parent, x, y);
            }
        }

        Console.WriteLine("Edges in the MST:");
        foreach (Edge edge in result)
            Console.WriteLine($"{edge.u} - {edge.v} : {edge.w}");
    }
}

public class Edge : IComparable<Edge>
{
    public int u, v, w;

    public Edge(int u, int v, int w)
    {
        this.u = u;
        this.v = v;
        this.w = w;
    }

    // 比较函数，按权值从小到大排序
    public int CompareTo(Edge other)
    {
        return this.w - other.w;
    }
}

public class KruskalAlgorithm
{
    public static void Main()
    {
        Graph g = new Graph(4, 5); // 4个节点，5条边
        g.AddEdge(0, 1, 10);
        g.AddEdge(0, 2, 6);
        g.AddEdge(0, 3, 5);
        g.AddEdge(1, 3, 15);
        g.AddEdge(2, 3, 4);

        g.KruskalMST();
    }
}

运行结果：

Edges in the MST:
2 - 3 : 4
0 - 3 : 5
0 - 1 : 10