Kruskal核心就是判断加入边之后是否成环，每次都是找一个权值最小的边，然后判断添加这条边，最小生成树是否会产生环也就是判断这条边的起始顶点和终止顶点是否已经在最小生成树的顶点集合中，说白了，就是判断两个顶点是否在同一个集合中，所以这里就是用到了 并查集。

本文参考：https://blog.csdn.net/junya_zhang/article/details/83584592
并查集参考：https://zhuanlan.zhihu.com/p/93647900

顶点：

    class Vertex
    {
        public int data;
        public Vertex(int data)
        {
            this.data = data;
        }
    }

边:

    class Edge
    {
        public int tail;
        public int head;
        public int width;
        public Edge(int tail, int head, int width)
        {
            this.tail = tail;
            this.head = head;
            this.width = width;
        }
    }

对边按权重从小到大排序:

class KruskalMinTree
    {
        EdgeK[] edge;
        public void EdgeSort(Edge[] edge)
        {
            for (int i = 0; i < edge.Length - 1; i++)
            {
                for (int j = i + 1; j < edge.Length; j++)
                {
                    if (edge[i].width > edge[j].width)
                    {
                        EdgeK temp = edge[j];
                        edge[j] = edge[i];
                        edge[i] = temp;
                    }
                }
            }
            this.edge = edge;
            Console.WriteLine("排序后的边的顺序为：");
            for (int i = 0; i < edge.Length; i++)
            {
                Console.WriteLine("[(" + edge[i].tail + "," + edge[i].head + ")" + "|" + edge[i].width + "]");
            }
        }

并查集 查询函数：

        public int Parent(int[] vex,int index)
        {
            while (vex[index] != -1)
            {
                index = vex[index];
            }
            return index;
        }

kruskal算法：

        public void Kruskal(int vexCount)
        {
            int[] vex = new int[vexCount];
            for (int i = 0; i < vex.Length; i++)
            {
                vex[i] = -1;
            }
            Console.Write("克鲁斯卡尔最小生成树：");
            for (int i = 0; i < edge.Length; i++)
            {
                int tailRoot = Parent(vex, edge[i].tail);
                int headRoot = Parent(vex, edge[i].head);

                if (tailRoot != headRoot)
                {
                    //并查集 合并
                    vex[tailRoot] = headRoot;//这里是将集合的根节点设置为headRoot
                    Console.Write("(" + edge[i].tail + "," + edge[i].head + ") ");
                }
            }
        }
    }

以下面的图进行Kruskal算法求最小生成树：

图

Main函数：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 数据结构代码篇
{
    class Program
    {
        static void Main(string[] args)
        {
            KruskalMinTree kruskal = new KruskalMinTree();
            Vertex vex0 = new Vertex(0);
            Vertex vex1 = new Vertex(1);
            Vertex vex2 = new Vertex(2);
            Vertex vex3 = new Vertex(3);
            Vertex vex4 = new Vertex(4);
            Vertex vex5 = new Vertex(5);
            Vertex vex6 = new Vertex(6);
            Vertex vex7 = new Vertex(7);
            Vertex vex8 = new Vertex(8);
            Vertex[] vex = { vex0, vex1, vex2, vex3, vex4, vex5, vex6, vex7, vex8 };
            Edge edge0 = new Edge(0, 1, 10);
            Edge edge1 = new Edge(0, 5, 11);
            Edge edge2 = new Edge(1, 2, 18);
            Edge edge3 = new Edge(1, 8, 12);
            Edge edge4 = new Edge(1, 6, 16);
            Edge edge5 = new Edge(5, 6, 17);
            Edge edge6 = new Edge(2, 8, 8);
            Edge edge7 = new Edge(2, 3, 22);
            Edge edge8 = new Edge(8, 3, 21);
            Edge edge9 = new Edge(6, 3, 24);
            Edge edge10 = new Edge(6, 7, 19);
            Edge edge11 = new Edge(3, 7, 16);
            Edge edge12 = new Edge(4, 7, 7);
            Edge edge13 = new Edge(3, 4, 20);
            Edge edge14 = new Edge(4, 5, 26);
            Edge[] edge = { edge0, edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8, edge9, edge10, edge11, edge12, edge13, edge14 };
            kruskal.EdgeSort(edge);
            kruskal.Kruskal(9);
            #endregion
            Console.ReadLine();
        }
    }
}

运行结果：

运行结果