时间戳

首页 > 技术文章 > 克鲁斯卡尔（Kruskal）算法（代码）

克鲁斯卡尔（Kruskal）算法（代码）

kokiafan 2021-05-17 16:21 原文

算法代码

C#代码

using System;
using System.Linq;

namespace Kruskal
{
    class Program
    {
        static void Main(string[] args)
        {
            Edge[] edges = new Edge[] {
                new Edge(){Begin = 4, End = 7, Weight = 7 },
                new Edge(){Begin = 2, End = 8, Weight = 8 },
                new Edge(){Begin = 0, End = 1, Weight = 10 },
                new Edge(){Begin = 0, End = 5, Weight = 11 },
                new Edge(){Begin = 1, End = 8, Weight = 12 },
                new Edge(){Begin = 3, End = 7, Weight = 16 },
                new Edge(){Begin = 1, End = 6, Weight = 16 },
                new Edge(){Begin = 5, End = 6, Weight = 17 },
                new Edge(){Begin = 1, End = 2, Weight = 18 },
                new Edge(){Begin = 6, End = 7, Weight = 19 },
                new Edge(){Begin = 3, End = 4, Weight = 20 },
                new Edge(){Begin = 3, End = 8, Weight = 21 },
                new Edge(){Begin = 2, End = 3, Weight = 22 },
                new Edge(){Begin = 3, End = 6, Weight = 24 },
                new Edge(){Begin = 4, End = 5, Weight = 26 },
            };
            int numberOfVertex = 9;

            Kruskal(edges, numberOfVertex);
        }

        static void Kruskal(Edge[] edges, int numberOfVertex)
        {
            bool isDemonstrate = false;              // （非必要代码）
            int[] vertex = new int[numberOfVertex];  // （非必要代码）T连通图的起始顶点。

            int[] parent = new int[numberOfVertex];  // 若连通图中存在环，那么从形成环的这条边的
                                                     // 两个顶点的任意顶点出发，都能沿着parent
                                                     // 数组找到相同的尾顶点下标。parent数组实际
                                                     // 存储着一个或多个或多个连通图。
            if (isDemonstrate)                       // （非必要代码）
            {
                for (int i = 0; i < numberOfVertex; i++)
                {
                    vertex[i] = i;
                }
            }


            for (int i = 0; i < numberOfVertex; i++) // 初始化路径的各尾顶点下标。
            {
                parent[i] = 0;
            }

            edges.OrderBy(e => e.Weight);             // 按权值的升序对边集进行排序。
            /** 从边集中逐个取出边，去测试这条边是否会构
                成环，不能构成环则将边的尾顶点下标加入
                parent数组中。*/
            for (int i = 0; i < edges.Length; i++)
            {
                Edge edge = edges[i];
                int n = Find(parent, edge.Begin),
                    m = Find(parent, edge.End);

                if (n != m)
                {
                    /** 若n与m不等，则此边未与现有生成树形成环路。
                        于是，将边的尾顶点下标放入数组的下标为边的
                        头顶点的parent数组中。表示现在该尾顶点已经
                        在生成树的集合中。*/
                    parent[n] = m;             // 将边的尾顶点下标放入数组parent。（两者任选其一）
                    //parent[m] = n;             // 将边的头顶点下标放入数组parent。（两者任选其一）
                    string result = $"({edge.Begin}, {edge.End}) = {edge.Weight}";
                    Console.WriteLine(result);       // 输出边。

                    if (isDemonstrate)               // （非必要代码）
                    {
                        Console.Write("非连通图头顶点下标vertex：");
                        PrintArray(vertex);
                        Console.Write("非连通图尾顶点下标parent：");       // 查看parent数组。
                        PrintArray(parent);
                    }
                }
            }
        }

        static int Find(int[] parent, int vertex)
        {
            while (parent[vertex] > 0)
            {
                vertex = parent[vertex];            // 寻找路径中下个顶点的下标。
            }
            return vertex;
        }

        static void PrintArray(int[] array)
        {
            Console.Write("[ ");
            for (int i = 0; i < array.Length - 1; i++)
            {                                       // 输出数组的前面n-1个
                Console.Write($"{ToInfinity(array[i])}, ");
            }
            if (array.Length > 0)                   // 输出数组的最后1个
            {
                int n = array.Length - 1;
                Console.Write($"{ToInfinity(array[n])}");
            }
            Console.WriteLine(" ]");
        }

        static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString();
    }

    class Edge
    {
        public int Begin { get; set; }
        public int End { get; set; }
        public int Weight { get; set; }
    }
}

/**
(4,7) = 7
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 0, 0, 0, 0, 7, 0, 0, 0, 0 ]
(2,8) = 8
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 0, 0, 8, 0, 7, 0, 0, 0, 0 ]
(0,1) = 10
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 0, 8, 0, 7, 0, 0, 0, 0 ]
(0,5) = 11
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 0, 7, 0, 0, 0, 0 ]
(1,8) = 12
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 0, 7, 8, 0, 0, 0 ]
(3,7) = 16
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 0, 0, 0 ]
(1,6) = 16
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 0, 0, 6 ]
(6,7) = 19
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 7, 0, 6 ] 
*/

对上面C#代码的补充

如果需要模拟前面文章中在连通图中寻找顶点的办法，那么可以将下面的代码添加到进来：


static void Kruskal2(Edge[] edges, int numberOfVertex)
{
    var sets = new List<VertexSet>();         // 用于存放各连通分量的列表。
                                              // 连通分量中顶点被放在一个顶点集合中。
    for (int i = 0; i < numberOfVertex; i++)  // 初始时，各顶点自成一个连通分量（顶点集合）。
    {
        sets.Add(new VertexSet(i));
    }

    edges.OrderBy(e => e.Weight);             // 按权值的升序对边集进行排序。
    /** 从边集中逐个取出边，去测试这条边是否会构
        成环，不能构成环则将分别包含边e的两个顶点
        的量连通分量（顶点集合）合并为tmp，然后从
        连通分量列表中删除这两个连通分量，并将新合
        成的连通分量tmp加入列表。*/
    for (int i = 0; i < edges.Length; i++)
    {
        Edge edge = edges[i];
        VertexSet n = Search(sets, edge.Begin),
            m = Search(sets, edge.End);

        if (n != m)
        {
            var tmp = n.Concat(m);
            sets.Remove(n);
            sets.Remove(m);
            sets.Add(tmp);

            string result = $"({edge.Begin}, {edge.End}) = {edge.Weight}";
            Console.WriteLine(result);       // 输出边。
        }
    }
    //Console.WriteLine($"Number of Vertex Set: {sets.Count}");
}

static VertexSet Search(IList<VertexSet> s, int code)
{
    return s.First(e => e.Has(code));
}

class Vertex
{
    public int Index { get; set; }
}

class VertexSet
{
    public VertexSet() { }

    public VertexSet(int index)
    {
        Add(new Vertex() { Index = index });
    }

    public HashSet<Vertex> Vertexes { get; } = new HashSet<Vertex>();

    public Vertex Add(Vertex v)
    {
        Vertexes.Add(v);
        return v;
    }

    public Vertex Remove(Vertex v)
    {
        if (Has(v))
        {
            return Vertexes.Remove(v) ? v : null;
        }
        return null;
    }

    public bool Has(Vertex v) => Has(v.Index);
    public bool Has(int index) => Vertexes.Any(e => e.Index == index);

    public VertexSet Concat(VertexSet second)
    {
        // 将当前顶点集合中的顶点和需要拼接的顶点集合中的顶点放入一个新的顶点集合vs中，
        // 并返回该新的顶点集合vs。
        VertexSet vs = new VertexSet();

        for (int i = 0; i < Vertexes.Count; i++)
        {
            vs.Add(Vertexes.ElementAt(i));
        }

        for (int i = 0; i < second.Vertexes.Count; i++)
        {
            vs.Add(second.Vertexes.ElementAt(i));
        }
        return vs;
    }
}

TypeScript代码

class Edge {
    Begin: number;
    End: number;
    Weight: number;
    constructor(begin: number, end: number, weight: number) {
        this.Begin = begin;
        this.End = end;
        this.Weight = weight;
    }
}

function kruskal(edges: Edge[], numberOfVertex: number) {
    let isDemonstrate: boolean = true;  // （非必要代码）
    let vertex: number[] = [];          // （非必要代码）T连通图的起始顶点。

    let parent: number[] = [];         /** 若连通图中存在环，那么从形成环的这条边的
                                        两个顶点的任意顶点出发，都能沿着parent
                                        数组找到相同的尾顶点下标。parent数组实际
                                        存储着一个或多个或多个连通图。*/

    if (isDemonstrate)                 // （非必要代码）
    {
        for (let i = 0; i < numberOfVertex; i++) {
            vertex[i] = i;
        }
    }

    for (let i = 0; i < numberOfVertex; i++)   // 初始化路径的各尾顶点下标。
    {
        parent[i] = 0;
    }

    edges.sort(e => e.Weight);         // 按权值的升序对边集进行排序。

    /** 从边集中逐个取出边，去测试这条边是否会构
        成环，不能构成环则将边的尾顶点下标加入
        parent数组中。*/
    for (let i = 0; i < edges.length; i++) {
        let edge: Edge = edges[i];
        let n: number = Find(parent, edge.Begin),
            m: number = Find(parent, edge.End);

        if (n != m) {
            /** 若n与m不等，则此边未与现有生成树形成环路。
                于是，将边的尾顶点下标放入数组的下标为边的
                头顶点的parent数组中。表示现在该尾顶点已经
                在生成树的集合中。*/
            parent[n] = m;             // 将边的尾顶点下标放入数组parent。（两者任选其一）
            //parent[m] = n;             // 将边的头顶点下标放入数组parent。（两者任选其一）
            let result: string = `(${edge.Begin}, ${edge.End}) = ${edge.Weight}`;
            console.log(result);       // 输出边。

            if (isDemonstrate)         // （非必要代码）
            {
                console.log(`非连通图头顶点下标vertex：${printArray(vertex)}`);
                // 查看parent数组。
                console.log(`非连通图尾顶点下标parent：${printArray(parent)}`);
            }


        }
    }
}

function Find(parent: number[], vertex: number): number {
    while (parent[vertex] > 0) {
        vertex = parent[vertex];       // 寻找路径中下个顶点的下标。
    }
    return vertex;
}

function printArray(array: number[]): string {
    let str: string[] = [];
    str.push("[ ");
    for (let i = 0; i < array.length - 1; i++) // 输出数组的前n-1个
    {
        str.push(`${toInfinity(array[i])}, `)
    }
    if (array.length > 0)                      // 输出数组的最后1个
    {
        let n: number = array.length - 1;
        str.push(`${toInfinity(array[n])}`);
    }
    str.push(" ]");
    return str.join("");
}

function toInfinity(i: number) {
    return i == Number.MAX_VALUE ? "∞" : i.toString();
}

function Main() {
    let edges: Edge[] = [
        new Edge(4, 7, 7),
        new Edge(2, 8, 8),
        new Edge(0, 1, 10),
        new Edge(0, 5, 11),
        new Edge(1, 8, 12),
        new Edge(3, 7, 16),
        new Edge(1, 6, 16),
        new Edge(5, 6, 17),
        new Edge(1, 2, 18),
        new Edge(6, 7, 19),
        new Edge(3, 4, 20),
        new Edge(3, 8, 21),
        new Edge(2, 3, 22),
        new Edge(3, 6, 24),
        new Edge(4, 5, 26),
    ];
    let numberOfVertex: number = 9;

    kruskal(edges, numberOfVertex);
}

Main();

/**
运行结果：
(4, 7) = 7
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 0, 0, 0, 0, 7, 0, 0, 0, 0 ]
(2, 8) = 8
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 0, 0, 8, 0, 7, 0, 0, 0, 0 ]
(0, 1) = 10
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 0, 8, 0, 7, 0, 0, 0, 0 ]
(0, 5) = 11
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 0, 7, 0, 0, 0, 0 ]
(1, 8) = 12
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 0, 7, 8, 0, 0, 0 ]
(3, 7) = 16
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 0, 0, 0 ]
(1, 6) = 16
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 0, 0, 6 ]
(6, 7) = 19
非连通图头顶点下标：[ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]
非连通图尾顶点下标：[ 1, 5, 8, 7, 7, 8, 7, 0, 6 ]
 */

参考资料：

《大话数据结构》 - 程杰 著 - 清华大学出版社 第252页

推荐阅读