加载中…
应用场景：网络铺设 · 聚类
交互式动画演示，可调整参数并单步执行。
全屏打开最小生成树（Minimum Spanning Tree, MST）：在连通无向带权图中，选取 n-1 条边使所有顶点连通，且边权之和最小。
| 性质 | 说明 |
|---|---|
| 边数 | 恰好 n-1 条 |
| 无环 | 是树 |
| 连通 | 所有顶点可达 |
| 权值和最小 | 全局最优 |
graph LR A -->|1| B A -->|4| C B -->|2| C B -->|5| D C -->|3| D
MST：选边 A-B(1)、B-C(2)、C-D(3)，总权 = 6。
贪心：将所有边按权值排序，从小到大依次选边，若该边连接的两个顶点不在同一连通分量（用并查集判断），则选入。
public int kruskal(int n, int[][] edges) {
// edges = {u, v, weight}
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int mstWeight = 0, edgeCount = 0;
for (int[] e : edges) {
if (uf.union(e[0], e[1])) {
mstWeight += e[2];
edgeCount++;
if (edgeCount == n - 1) break;
}
}
return edgeCount == n - 1 ? mstWeight : -1; // -1 表示不连通
}
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false;
if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
}贪心：从一个顶点出发，每次选连接已选集合与未选集合的最小边，将新顶点加入。
类似 Dijkstra，但维护的是"到已选集合的最小边权"而非"到源点的最短距离"。
public int prim(List<int[]>[] graph, int start) {
int n = graph.length;
boolean[] visited = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// {顶点, 边权}
pq.offer(new int[]{start, 0});
int mstWeight = 0, edgeCount = 0;
while (!pq.isEmpty() && edgeCount < n) {
int[] cur = pq.poll();
int u = cur[0], w = cur[1];
if (visited[u]) continue;
visited[u] = true;
mstWeight += w;
edgeCount++;
for (int[] edge : graph[u]) {
int v = edge[0], ew = edge[1];
if (!visited[v]) pq.offer(new int[]{v, ew});
}
}
return edgeCount == n ? mstWeight : -1;
}| 维度 | Kruskal | Prim |
|---|---|---|
| 核心 | 选边（全局排序） | 选点（逐步扩展） |
| 数据结构 | 并查集 | 优先队列 / 数组 |
| 适合 | 稀疏图（E 小） | 稠密图（E ≈ V²） |
| 时间 | O(E log E) | O(E log V) / O(V²) |
| 是否需要连通 | 可处理森林 | 需要连通图 |
对图的任意切割，跨越切割的最小权边一定属于某棵 MST。
这是 Kruskal 和 Prim 正确性的理论基础。
对图中的任意环，环上最大权边一定不属于 MST。
| 应用 | 说明 |
|---|---|
| 网络设计 | 最低成本连通所有节点 |
| 聚类分析 | 删除 MST 中最大边 → 两类聚类 |
| 近似 TSP | MST 的 DFS 序给出 2 倍近似 |
| 瓶颈路 | 最小瓶颈路 = MST 上的路径 |
public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.abs(points[i][0] - points[j][0])
+ Math.abs(points[i][1] - points[j][1]);
edges.add(new int[]{i, j, dist});
}
}
return kruskal(n, edges.toArray(new int[0][]));
}parent[i] = i。