【数据结构与算法 | 图篇】最小生成树之Kruskal(克鲁斯卡尔)算法

1. 前言

克鲁斯卡尔算法（Kruskal's algorithm）是一种用于寻找加权图的最小生成树（Minimum Spanning Tree, MST）的经典算法。这种算法是由约瑟夫·克鲁斯卡尔（Joseph Kruskal）提出的，并且适用于所有类型的加权无向图，特别是那些边比较稀疏的图。

Prim算法更偏重于图的顶点，而克鲁斯卡尔算法更偏重于图的边。

2. 基本步骤

1. 排序：首先将图中的所有边按照权重（cost）从小到大进行排序。
2. 初始化：创建一个空集合来保存最小生成树中的边。
3. 遍历边：依次检查每一条边，检查顺序基于权重的大小。对于每一条边 `(u, v)`：如果加入这条边不会在已选择的边中形成环，则将这条边加入到最小生成树中。如果加入这条边会导致环的形成，则跳过这条边。
4. 终止条件：重复上述过程，直到最小生成树包含了 `n - 1` 条边（其中 `n` 是顶点的数量），或者没有更多的边可以添加为止。

3. 代码

public class Kruskal {// 静态内部类static class Edge implements Comparable<Edge>{// 顶点集合,构造器赋值，用于toString方法List<Vertex> vertices;// 下列两属性是定点集合的索引，比如索引0代表顶点v1int start;int end;int weight;public Edge(int start, int end, int weight) {this.start = start;this.end = end;this.weight = weight;}public Edge(List<Vertex> vertices, int start, int end, int weight) {this.vertices = vertices;this.start = start;this.end = end;this.weight = weight;}@Overridepublic int compareTo(Edge o) {return Integer.compare(this.weight, o.weight);}@Overridepublic String toString() {return "v" + vertices.get(start).name + "<=>" + "v"+vertices.get(end).name + "  " + "(" + weight + ")";}}public static void main(String[] args) {List<Vertex> vertices = new ArrayList<>();Vertex v1 = new Vertex("0");Vertex v2 = new Vertex("1");Vertex v3 = new Vertex("2");Vertex v4 = new Vertex("3");Vertex v5 = new Vertex("4");Vertex v6 = new Vertex("5");Vertex v7 = new Vertex("6");vertices.add(v1);vertices.add(v2);vertices.add(v3);vertices.add(v4);vertices.add(v5);vertices.add(v6);vertices.add(v7);List<Edge> edges = new ArrayList<>();// 由于处理的是加权无向图，所以start:0, end:1与start:1, end:0无区别edges.add(new Edge(vertices, 0, 1, 2));edges.add(new Edge(vertices, 0, 2, 4));edges.add(new Edge(vertices, 0, 3, 1));edges.add(new Edge(vertices, 1, 3, 3));edges.add(new Edge(vertices, 1, 4, 10));edges.add(new Edge(vertices, 2, 3, 2));edges.add(new Edge(vertices, 2, 5, 5));edges.add(new Edge(vertices, 3, 4, 7));edges.add(new Edge(vertices, 3, 5, 8));edges.add(new Edge(vertices, 3, 6, 4));edges.add(new Edge(vertices, 4, 6, 6));edges.add(new Edge(vertices, 5, 6, 1));//将边的集合按照从小到大的顺序排列PriorityQueue<Edge> queue = new PriorityQueue<>(edges);kruskal(vertices.size(), queue);}public static void kruskal(int size, PriorityQueue<Edge> queue) {// 创建一个空集合来保存最小生成树中的边。List<Edge> list = new ArrayList<>();// 最小生成树的顶点数为size个，所以只需要找到size-1条边即可while (list.size() < size - 1){// 弹出边权重最小的边判断Edge poll = queue.poll();// 并查集:用来判断该边加入是否会相交，如果会，则跳过该边DisjointSet set = new DisjointSet(size);int i = set.find(poll.start);int j = set.find(poll.end);// 如果不相交if(i != j){list.add(poll);// 将两点相交set.union(i, j);}}for (Edge e : list){System.out.println(e);}}
}

输出：

v0<=>v3  (1)
v5<=>v6  (1)
v2<=>v3  (2)
v0<=>v1  (2)
v1<=>v3  (3)
v0<=>v2  (4)

4. 图注

初始时顶点图:

最小生成树的图:

由图：当（v3->v4）(v4->v7) （v7->v6）三顶点已经连通，判断(v3->v6)时，find(2) == find(5)，即两个顶点已经连通，(如果加入该边会形成环)所以跳过该边。