【原】技术图文：如何利用C# 实现 Kruskal 最小生成树算法？

老马的程序人生 2020-08-17

展开全文

背景

以前我写过一些图文来介绍有关数据结构与算法的知识：

本次，向大家介绍图论中构造最小生成树的 Kruskal 算法。

技术分析

Kruskal 算法：

例子：

该例子演示了一个含有6个结点，10条边的连通网，通过 Kruskal 算法逐步演化为含有6个结点，5条边的连通子网的过程，即构造最小生成树的过程。

代码实现

Step1 构造边表结点的结构 EdgeNode。

public class EdgeNode
{
    /// <summary>
    /// 获取边终点在顶点数组中的位置
    /// </summary>
    public int Index { get; }

    /// <summary>
    /// 获取边上的权值
    /// </summary>
    public double Weight { get; }

    /// <summary>
    /// 获取或设置下一个邻接点
    /// </summary>
    public EdgeNode Next { get; set; }

    /// <summary>
    /// 初始化EdgeNode类的新实例
    /// </summary>
    /// <param name="index">边终点在顶点数组中的位置</param>
    /// <param name="weight">边上的权值</param>
    /// <param name="next">下一个邻接点</param>
    public EdgeNode(int index, double weight = 0.0, EdgeNode next = null)
    {
        if (index < 0)
            throw new ArgumentOutOfRangeException();

        Index = index;
        Weight = weight;
        Next = next;
    }
}

Step2 构造顶点表结点的结构 VertexNode。

public class VertexNode
{
    /// <summary>
    /// 获取或设置顶点的名字
    /// </summary>
    public string VertexName { get; set; }

    /// <summary>
    /// 获取或设置顶点是否被访问
    /// </summary>
    public bool Visited { get; set; }

    /// <summary>
    /// 获取或设置顶点的第一个邻接点
    /// </summary>
    public EdgeNode FirstNode { get; set; }

    /// <summary>
    /// 初始化VertexNode类的新实例
    /// </summary>
    /// <param name="vName">顶点的名字</param>
    /// <param name="firstNode">顶点的第一个邻接点</param>
    public VertexNode(string vName, EdgeNode firstNode = null)
    {
        VertexName = vName;
        Visited = false;
        FirstNode = firstNode;
    }
}

Step3 构造利用邻接表存储图的结构AdGraph。

通过 AdGraph 的索引器可以为顶点表赋值，通过 AddEdge 方法可以为边表赋值。

public class AdGraph
{
    private readonly VertexNode[] _vertexList; //结点表

    /// <summary>
    /// 获取图的结点数
    /// </summary>
    public int VertexCount { get; }

    /// <summary>
    /// 初始化AdGraph类的新实例
    /// </summary>
    /// <param name="vCount">图中结点的个数</param>
    public AdGraph(int vCount)
    {
        if (vCount <= 0)
            throw new ArgumentOutOfRangeException();

        VertexCount = vCount;
        _vertexList = new VertexNode[vCount];
    }

    /// <summary>
    /// 获取或设置图中各结点的名称
    /// </summary>
    /// <param name="index">结点名称从零开始的索引</param>
    /// <returns>指定索引处结点的名称</returns>
    public string this[int index]
    {
        get
        {
            if (index < 0 || index > VertexCount - 1)
                throw new ArgumentOutOfRangeException();

            return _vertexList[index] == null
                ? "NULL"
                : _vertexList[index].VertexName;
        }
        set
        {
            if (index < 0 || index > VertexCount - 1)
                throw new ArgumentOutOfRangeException();

            if (_vertexList[index] == null)
                _vertexList[index] = new VertexNode(value);
            else
                _vertexList[index].VertexName = value;
        }
    }

    /// <summary>
    /// 得到结点在结点表中的位置
    /// </summary>
    /// <param name="vertexName">结点的名称</param>
    /// <returns>结点的位置</returns>
    private int GetIndex(string vertexName)
    {
        int i;
        for (i = 0; i < VertexCount; i++)
        {
            if (_vertexList[i] != null && _vertexList[i].VertexName == vertexName)
                break;
        }
        return i == VertexCount ? -1 : i;
    }

    /// <summary>
    /// 给图加边
    /// </summary>
    /// <param name="startVertexName">起始结点的名字</param>
    /// <param name="endVertexName">终止结点的名字</param>
    /// <param name="weight">边上的权值</param>
    public void AddEdge(string startVertexName, string endVertexName
        , double weight = 0.0)
    {
        int i = GetIndex(startVertexName);
        int j = GetIndex(endVertexName);

        if (i == -1 || j == -1)
            throw new Exception("图中不存在该边.");

        EdgeNode temp = _vertexList[i].FirstNode;
        if (temp == null)
        {
            _vertexList[i].FirstNode = new EdgeNode(j, weight);
        }
        else
        {
            while (temp.Next != null)
                temp = temp.Next;
            temp.Next = new EdgeNode(j, weight);
        }
    }
}

上面例子对应的邻接表如下所示：

Step4 构造最小生成树结点的结构 SpanTreeNode。

public class SpanTreeNode
{
    /// <summary>
    /// 获取或设置结点本身的名称
    /// </summary>
    public string SelfName { get; }

    /// <summary>
    /// 获取或设置结点双亲的名称
    /// </summary>
    public string ParentName { get; }

    /// <summary>
    /// 获取或设置边的权值
    /// </summary>
    public double Weight { get; set; }

    /// <summary>
    /// 构造SpanTreeNode实例
    /// </summary>
    /// <param name="selfName">结点本身的名称</param>
    /// <param name="parentName">结点双亲的名称</param>
    /// <param name="weight">边的权值</param>
    public SpanTreeNode(string selfName, string parentName, double weight)
    {
        if (string.IsNullOrEmpty(selfName) || string.IsNullOrEmpty(parentName))
            throw new ArgumentNullException();

        SelfName = selfName;
        ParentName = parentName;
        Weight = weight;
    }
}

Step5 构造边的结构 Edge。

internal class Edge
{
    /// <summary>
    /// 起点编号
    /// </summary>
    public int Begin { get;}

    /// <summary>
    /// 终点编号
    /// </summary>
    public int End { get; }

    /// <summary>
    /// 权值
    /// </summary>
    public double Weight { get; }

    /// <summary>
    /// 创建一个 Edge 类的新实例
    /// </summary>
    /// <param name="begin">起点编号</param>
    /// <param name="end">终点编号</param>
    /// <param name="weight">权值</param>

    public Edge(int begin, int end, double weight = 0.0)
    {
        Begin = begin;
        End = end;
        Weight = weight;
    }
}

Step6 获取边集合的方法 GetEdges。

private Edge[] GetEdges()
{
    for (int i = 0; i < VertexCount; i++)
        _vertexList[i].Visited = false;

    List<Edge> result = new List<Edge>();

    for (int i = 0; i < VertexCount; i++)
    {
        _vertexList[i].Visited = true;
        EdgeNode p = _vertexList[i].FirstNode;
        while (p != null)
        {
            if (_vertexList[p.Index].Visited == false)
            {
                Edge edge = new Edge(i, p.Index, p.Weight);
                result.Add(edge);
            }
            p = p.Next;
        }
    }
    return result.OrderBy(a => a.Weight).ToArray();
}

上面例子对应的边的集合如下所示：

Step7 获取最小生成树的 Kruskal 算法。

private int Find(int[] parent, int f)
{
    while (parent[f] > 0)
        f = parent[f];
    return f;
}

/// <summary>
/// 克鲁斯卡尔算法 最小生成树
/// </summary>
/// <returns></returns>
public SpanTreeNode[] MiniSpanTree()
{
    int[] parent = new int[VertexCount];
    for (int i = 0; i < VertexCount; i++)
    {
        parent[i] = 0;
    }
    SpanTreeNode[] tree = new SpanTreeNode[VertexCount];
    int count = 0;
    Edge[] edges = GetEdges();

    for (int i = 0; i < edges.Length; i++)
    {
        int begin = edges[i].Begin;
        int end = edges[i].End;
        int n = Find(parent, begin);
        int m = Find(parent, end);
        if (n != m)
        {
            if (i == 0)
            {
                tree[count] = new SpanTreeNode(_vertexList[begin].VertexName, "NULL", 0.0);
                count++;
            }
            parent[n] = m;
            tree[count] = new SpanTreeNode(_vertexList[end].VertexName,
                _vertexList[begin].VertexName, edges[i].Weight);
            count++;
        }
    }
    return tree;
}

总结

到此为止代码部分就全部介绍完了，我们来看一下上面例子的应用。

static void Main(string[] args)
{
    AdGraph alg = new AdGraph(6);
    alg[0] = "V0";
    alg[1] = "V1";
    alg[2] = "V2";
    alg[3] = "V3";
    alg[4] = "V4";
    alg[5] = "V5";
    alg.AddEdge("V0", "V1", 6);
    alg.AddEdge("V0", "V2", 1);
    alg.AddEdge("V0", "V3", 5);
    alg.AddEdge("V1", "V0", 6);
    alg.AddEdge("V1", "V2", 5);
    alg.AddEdge("V1", "V4", 3);
    alg.AddEdge("V2", "V0", 1);
    alg.AddEdge("V2", "V1", 5);
    alg.AddEdge("V2", "V3", 7);
    alg.AddEdge("V2", "V4", 5);
    alg.AddEdge("V2", "V5", 4);
    alg.AddEdge("V3", "V0", 5);
    alg.AddEdge("V3", "V2", 7);
    alg.AddEdge("V3", "V5", 2);
    alg.AddEdge("V4", "V1", 3);
    alg.AddEdge("V4", "V2", 5);
    alg.AddEdge("V4", "V5", 6);
    alg.AddEdge("V5", "V2", 4);
    alg.AddEdge("V5", "V3", 2);
    alg.AddEdge("V5", "V4", 6);
    SpanTreeNode[] tree = alg.MiniSpanTree();
    double sum = 0;
    for (int i = 0; i < tree.Length; i++)
    {
        string str = "(" + tree[i].ParentName + ","
                + tree[i].SelfName + ") Weight:"
                + tree[i].Weight;
        Console.WriteLine(str);
        sum += tree[i].Weight;
    }
    Console.WriteLine(sum);
}