代码与动画 KRUSKAL · MST
Kruskal 最小生成树.
按权重尝试连接两个分量，使用并查集排除形成环的边。
时间 O(E log E + Eα(V))空间 O(V + E)无向带权图
原理与执行逻辑
按权重从小到大检查无向边，优先连接尚未连通的两个分量。并查集判断两端是否已经连通，避免选入形成环的边。
执行步骤
- 每个顶点初始化为独立集合，将边按权重排序。
- 查找当前边两端的集合代表。
- 代表相同时跳过；不同时选边，并按集合大小合并。
- 扫描结束后输出总权重与选中边；不连通图得到最小生成森林。
关键理解
选中的边始终无环。连接当前两个分量的最小可用边可以加入某棵最小生成树；并查集记录连通关系，不负责比较权重。
简短示例
A-B 权重 1、B-C 权重 2、A-C 权重 4。先选前两条，总权重 3；最后一条的两端已连通，跳过。
代码与执行动画
STEP 0 / 15function kruskal(vertices, edges) { const parent = Object.fromEntries(vertices.map(v => [v, v])); const size = Object.fromEntries(vertices.map(v => [v, 1])); function find(v) { if (parent[v] !== v) parent[v] = find(parent[v]); return parent[v]; } const result = []; let cost = 0; for (const edge of [...edges].sort((a, b) => a.weight - b.weight)) { let a = find(edge.from), b = find(edge.to); if (a === b) continue; if (size[a] < size[b]) [a, b] = [b, a]; parent[b] = a; size[a] += size[b]; result.push(edge); cost += edge.weight; } return {edges: result, cost};}累计权重 0分量 6
当前数据正在操作已访问 / 命中标记 / 指针
0
排序所有边
按权重从小到大检查，初始每个顶点是独立分量。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
Kruskal 最小生成树的操作规则
固定顶点 A–F，采用路径压缩与按大小合并。图不连通时输出最小生成森林，并标出分量数量；重复无向边保留最小权重。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
先用曼哈顿距离构建边，再运行 Kruskal 与并查集。
扩展应用：按高度激活或按边权合并，直到起点与终点连通；答案是路径最大高度。