Kruskal算法剖析与py/cpp/Java语言实现

- 一、Kruskal算法的基本概念
- - 1.1 最小生成树
  - 1.2 Kruskal算法核心思想
- 二、Kruskal算法的执行流程
- 三、Kruskal算法的代码实现
- - 3.1 Python实现
  - 3.2 C++实现
  - 3.3 Java实现
- 四、算法复杂度分析
- - 4.1 时间复杂度
  - 4.2 空间复杂度
- 五、Kruskal算法应用场景
- - 5.1 网络布线
  - 5.2 聚类分析
  - 5.3 电路设计
- 总结

图论算法中最小生成树（Minimum Spanning Tree，MST）问题是一个经典且具有重要实际意义的问题。Kruskal算法作为求解最小生成树的常用算法之一，以其简洁的思想和高效的实现，在网络规划、电路设计、聚类分析等众多领域发挥着关键作用。本文我将深入剖析Kruskal算法的原理、详细介绍其执行流程，并分别使用Python、C++和Java三种编程语言进行代码实现，帮你全面掌握这一经典算法。

一、Kruskal算法的基本概念

1.1 最小生成树

对于一个连通无向图 (G=(V, E))，其中 (V) 是顶点集合，(E) 是边集合，其最小生成树是一个包含图中所有顶点的树状子图 (T=(V, E’))（(E’ \subseteq E)），并且满足边的权值之和最小。最小生成树具有以下特点：

包含图中的所有顶点，即顶点数为 (|V|)。
边数为 (|V| - 1)，因为树的边数比顶点数少 1。
不存在回路（环），确保其树状结构。
边的权值总和在所有满足上述条件的子图中最小。

1.2 Kruskal算法核心思想

Kruskal算法基于贪心策略，其核心思想是：从图中所有边中选择权值最小的边，若该边的两个顶点不在同一个连通分量中，则将这条边加入到最小生成树中；重复这个过程，直到最小生成树包含图中的所有顶点，或者边的数量达到 (|V| - 1) 为止。通过不断选择局部最优（权值最小且不构成回路的边），最终得到全局最优的最小生成树。

二、Kruskal算法的执行流程

初始化：将图中的每条边按照权值从小到大进行排序。同时，初始化一个用于存储最小生成树的边集合 mst_edges，以及一个用于判断顶点是否在同一个连通分量的并查集数据结构（可以使用数组或更复杂的并查集类实现）。
遍历边：依次遍历排序后的边集合，对于每条边 ((u, v, w))（其中 (u) 和 (v) 是边的两个顶点，(w) 是边的权值）：
- 使用并查集判断顶点 (u) 和 (v) 是否在同一个连通分量中。如果不在同一个连通分量，说明将这条边加入最小生成树不会形成回路，则将该边加入到 mst_edges 中，并通过并查集将 (u) 和 (v) 所在的连通分量合并。
- 如果顶点 (u) 和 (v) 已经在同一个连通分量中，说明加入这条边会形成回路，直接跳过该边。
结束条件：当最小生成树的边数达到 (|V| - 1) 时，或者遍历完所有边后，算法结束。此时，mst_edges 中存储的边集合即为图的最小生成树。

三、Kruskal算法的代码实现

3.1 Python实现

def find(parent, i):if parent[i] == i:return ireturn find(parent, parent[i])def union(parent, rank, x, y):xroot = find(parent, x)yroot = find(parent, y)if rank[xroot] < rank[yroot]:parent[xroot] = yrootelif rank[xroot] > rank[yroot]:parent[yroot] = xrootelse:parent[yroot] = xrootrank[xroot] += 1def kruskalMST(graph):result = []i, e = 0, 0edges = []for u in range(len(graph)):for v, w in enumerate(graph[u]):if w > 0:edges.append((u, v, w))edges.sort(key=lambda item: item[2])parent = []rank = []for v in range(len(graph)):parent.append(v)rank.append(0)while e < len(graph) - 1 and i < len(edges):u, v, w = edges[i]i = i + 1x = find(parent, u)y = find(parent, v)if x != y:e = e + 1result.append((u, v, w))union(parent, rank, x, y)return resultgraph = [[0, 10, 6, 5, 0, 0],[10, 0, 0, 15, 0, 0],[6, 0, 0, 4, 7, 0],[5, 15, 4, 0, 0, 8],[0, 0, 7, 0, 0, 9],[0, 0, 0, 8, 9, 0]
]
print(kruskalMST(graph))

3.2 C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;class Edge {
public:int src, dest, weight;Edge(int s, int d, int w) : src(s), dest(d), weight(w) {}
};bool compareEdges(const Edge& a, const Edge& b) {return a.weight < b.weight;
}int find(vector<int>& parent, int i) {if (parent[i] == i)return i;return find(parent, parent[i]);
}void unionSet(vector<int>& parent, vector<int>& rank, int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot])parent[xroot] = yroot;else if (rank[xroot] > rank[yroot])parent[yroot] = xroot;else {parent[yroot] = xroot;rank[xroot]++;}
}vector<Edge> kruskalMST(vector<vector<int>>& graph) {vector<Edge> edges;for (int u = 0; u < graph.size(); u++) {for (int v = 0; v < graph.size(); v++) {if (graph[u][v] > 0) {edges.push_back(Edge(u, v, graph[u][v]));}}}sort(edges.begin(), edges.end(), compareEdges);vector<int> parent(graph.size());vector<int> rank(graph.size(), 0);for (int i = 0; i < graph.size(); i++) {parent[i] = i;}vector<Edge> result;int e = 0, i = 0;while (e < graph.size() - 1 && i < edges.size()) {Edge next_edge = edges[i++];int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);if (x != y) {e++;result.push_back(next_edge);unionSet(parent, rank, x, y);}}return result;
}int main() {vector<vector<int>> graph = {{0, 10, 6, 5, 0, 0},{10, 0, 0, 15, 0, 0},{6, 0, 0, 4, 7, 0},{5, 15, 4, 0, 0, 8},{0, 0, 7, 0, 0, 9},{0, 0, 0, 8, 9, 0}};vector<Edge> mst = kruskalMST(graph);for (const auto& edge : mst) {cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;}return 0;
}

3.3 Java实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;class Edge implements Comparable<Edge> {int src, dest, weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}@Overridepublic int compareTo(Edge other) {return Integer.compare(this.weight, other.weight);}
}class Kruskal {static int find(int[] parent, int i) {if (parent[i] == i)return i;return find(parent, parent[i]);}static void union(int[] parent, int[] rank, int x, int y) {int xroot = find(parent, x);int yroot = find(parent, y);if (rank[xroot] < rank[yroot])parent[xroot] = yroot;else if (rank[xroot] > rank[yroot])parent[yroot] = xroot;else {parent[yroot] = xroot;rank[xroot]++;}}static List<Edge> kruskalMST(int[][] graph) {List<Edge> edges = new ArrayList<>();for (int u = 0; u < graph.length; u++) {for (int v = 0; v < graph.length; v++) {if (graph[u][v] > 0) {edges.add(new Edge(u, v, graph[u][v]));}}}Collections.sort(edges);int[] parent = new int[graph.length];int[] rank = new int[graph.length];for (int i = 0; i < graph.length; i++) {parent[i] = i;}List<Edge> result = new ArrayList<>();int e = 0, i = 0;while (e < graph.length - 1 && i < edges.size()) {Edge nextEdge = edges.get(i++);int x = find(parent, nextEdge.src);int y = find(parent, nextEdge.dest);if (x != y) {e++;result.add(nextEdge);union(parent, rank, x, y);}}return result;}
}public class KruskalAlgorithm {public static void main(String[] args) {int[][] graph = {{0, 10, 6, 5, 0, 0},{10, 0, 0, 15, 0, 0},{6, 0, 0, 4, 7, 0},{5, 15, 4, 0, 0, 8},{0, 0, 7, 0, 0, 9},{0, 0, 0, 8, 9, 0}};List<Edge> mst = Kruskal.kruskalMST(graph);for (Edge edge : mst) {System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);}}
}

四、算法复杂度分析

4.1 时间复杂度

Kruskal算法的时间复杂度主要由两部分组成：

对边进行排序的时间复杂度：假设图中有 (E) 条边，使用比较排序算法（如快速排序、归并排序）对边按权值排序，时间复杂度为 (O(E \log E))。由于在连通图中 (E \geq V - 1)，所以 (O(E \log E)) 可以近似为 (O(E \log V))。
遍历边并判断连通性和合并连通分量的时间复杂度：在最坏情况下，需要遍历所有 (E) 条边，每次遍历需要使用并查集判断顶点的连通性和合并连通分量，其时间复杂度近似为 (O(\alpha(V)))（(\alpha(V)) 是阿克曼函数的反函数，增长极其缓慢，在实际应用中可近似看作常数时间）。因此，遍历边的总时间复杂度为 (O(E \alpha(V)))，可近似为 (O(E))。

综合以上两部分，Kruskal算法的时间复杂度为 (O(E \log V))，其中 (E) 是边的数量，(V) 是顶点的数量。