最小生成树：Prim 与 Kruskal
给一张加权无向连通图，要选出一组 edge 把所有 vertex 连起来、不留 cycle、且总 weight 最小——这就是 minimum spanning tree (MST)。先用 cut theorem 说明 greedy 为何正确，再单步运行两种经典 greedy algorithm:Prim（从一个 vertex 长出一棵树）与 Kruskal（按 edge weight 从小到大、用 union-find 合并森林）。两者起点不同，但总会得到相同的最小总 weight。每个 demo 都可以更换示例图、单步执行、自动播放。Kruskal 用到 union-find（并查集）判 cycle，这一结构的细节见 并查集 · Union-Find。本页四节：cut theorem → Prim → Kruskal → 应用实例。
1 · Spanning tree、minimum spanning tree 与 cut theorem
给一张连通的加权无向图，spanning tree 就是「用图里的 edge 把所有 n 个 vertex 连起来、且不含 cycle」的一组 edge。它必然恰好有 n−1 条 edge——少一条就连不全，多一条就一定形成 cycle。在所有 spanning tree 里，edge weight 之和最小的那一（些）棵，就是 minimum spanning tree (MST)。
三者等价（对 n 个 vertex 的连通图）：「无 cycle 且连通」⟺「连通且恰好 n−1 条 edge」⟺「无 cycle 且恰好 n−1 条 edge」。所以求 MST = 在所有 edge 里挑出 n−1 条、既连通又无 cycle、且总 weight 最小。
1.1 · Cut theorem:greedy 为什么是对的
把 vertex 任意分成两个非空的部分（一个 cut），两端分属不同部分的 edge 叫 crossing edge。cut theorem 说：**任一 cut 中，weight 最小的那条 crossing edge，一定属于某棵 minimum spanning tree。**下面点击 vertex，在「蓝色一侧 / 灰色一侧」之间切换它的归属，虚线表示当前的 crossing edge，绿色那条是其中最小的。
为什么安全？ 设最小 crossing edge 是 e。假如某棵 MST 不含 e，那么把 e 加进去会形成唯一一个 cycle，这个 cycle 必然还跨过 cut、于是含有另一条 crossing edge e′。因为 e 是 crossing edge 里最小的，把 e′ 换成 e 不会让总 weight 变大——于是得到一棵 weight 不增、且含 e 的 spanning tree。所以总有一棵 MST 含 e。**Prim 和 Kruskal 每一步加的 edge，本质都是某个 cut 的最小 crossing edge。**具体过程见下面 Prim 与 Kruskal 两节。
唯一性： 当所有 edge weight 两两不同时，每个 cut 的最小 crossing edge 唯一，MST 也唯一（像「经典 6 点图」）。若存在相等 weight，可能有多棵 weight 相同的 MST——但最小总 weight 始终唯一。
2 · Prim：从一个 vertex 长出整棵树
Prim 的视角是「一棵不断长大的树」。从任一起点出发，把整张图切成「已在树中的 vertex」和「还没并进来的 vertex」两侧——这正是一个 cut。每步在所有 crossing edge 里挑 weight 最小的一条，把它和另一端的新 vertex 一起并入树。重复 n−1 次，树就覆盖了全部 vertex。
其一，起点单独成树。
其二，看「树 ↔ 树外」的所有 crossing edge，取其中 weight 最小的一条。
其三，把这条 edge 加进 MST，它另一端的新 vertex 并入树。
其四，回到第二步，直到全部 n 个 vertex 都在树里（共加了 n−1 条 edge）。
由 cut theorem（见上面 cut theorem 一节），每步选的最小 crossing edge 都是安全的，所以 greedy 进行到底即得 minimum spanning tree。下面点「下一步」逐步执行。
和 cut theorem 的对应： 每一步「已在树中的 vertex」就是 cut 的一侧，候选 crossing edge 就是该 cut 的 crossing edge，选最小的那条正是定理保证安全的 edge。Prim 始终只维护一棵连通的树，逐层向外扩展。另一种走法见下面 Kruskal。
3 · Kruskal：按 edge weight 排序、union-find 判 cycle
Kruskal 的视角是「一片正在合并的森林」。一开始每个 vertex 自成一棵小树。把所有 edge 按 weight 从小到大排好，逐条尝试：这条 edge 的两端若不在同一棵树里，就把它加进 MST，并把两棵树合并；若已经同属一棵树，加它会形成 cycle,丢弃。凑齐 n−1 条 edge 时，森林并成了一棵树，就是 minimum spanning tree。
怎么快速判「两端是否同一棵树」？ 用 union-find (DSU):find(x) 找 x 所在集合的 root / representative，两端 find 相同 ⟹ 同集合 ⟹ 形成 cycle；不同就 union 合并。配合 path compression，每次判定几乎是 O(1)。
3.1 · 预备：union-find (DSU) 的 find / union
**前置知识：**这里只把并查集当现成结构使用（下面是一个独立的小 demo）。它本身的原理——为什么 find 接近 O(1)、quick-find / quick-union / weighted / path compression 四步如何逐层优化——单独成了一个系列：并查集 · Union-Find，可先阅读该系列补足这块基础。
Kruskal 每一步只需判断：这两个 vertex 是否已经在同一棵树里？这一判断完全交给 union-find。先把它从图里拆出来单独演示：6 个元素一开始各自成组。union(a, b) 找到两边的 root，把一个 root 挂到另一个 root 下，两组合并；find(x)
从 x 顺着 parent pointer 一路走到 root（集合的 representative）。开启 path compression 后，find 会把沿途的 node 直接挂到 root 下，树随之变扁——这正是其复杂度接近 O(1) 的原因。
接回 Kruskal: 下面每试一条 edge
，就是先 find(u)、find(v)——两 root 不同说明分属两棵树，加 edge 并 union；两 root 相同说明早就连通，加它会形成 cycle，丢弃。
每条被加入的 edge，也对应一个 cut（它跨在两棵当前的树之间），且是该 cut 里最小的 crossing edge——所以同样由 cut theorem（见上面 cut theorem 一节）保证正确。下面点「下一步」逐条考察 edge。
Prim vs Kruskal——同一个 greedy 的两种走法。 Prim 始终只维护一棵树，每步在「树 ↔ 树外」的 crossing edge 里取最小，在稠密图（edge 多）上更高效。Kruskal 维护一片森林，全局按 edge weight 从小到大合并，需要先排序、再用 union-find 判 cycle，在稀疏图（edge 少）上更合适。两者都直接建立在 cut theorem 之上，因此最小总 weight 必然相同（weight 各不相同时树形也相同）。
4 · 应用实例：MST 究竟用在何处
把抽象的图换成地图上的一组点（城市 / 机房 / 传感器），任意两点都能连、代价 = 距离。最小生成树立刻有了两个直接用途：其一，用最短的总线缆把所有点连通（铺光纤 / 管网 / 电网），以及 其二，聚类——把 MST 里最长的几条边剪掉，剩下的连通块就是聚集成团的簇。拖动点、调整簇数，实时观察这两种用途。本系列的 Prim / Kruskal 与 cut theorem 见上面对应三节。
全连接需要 条边（灰线）,MST 只挑其中 条、总长最小的（绿线）且不成环。切边聚类：把 MST 的 条最长边剪断，正好分出 k 个簇——这就是 single-linkage 层次聚类。
4.1 · 同一棵树，还藏在这些地方
「用最便宜的边把该连的连起来 / 按最贵的边把该分的分开」这一思路，在工程中反复出现：
网络与基建——铺设最省的光纤骨干、城市管网、电网、芯片内的时钟树；数据中心 / 传感器集群用最低总成本保持连通。
聚类与图像分割——single-linkage 层次聚类 = 在 MST 上由长到短切边；经典图像分割 Felzenszwalb-Huttenlocher 直接在像素图的 MST 上合并区域。
和最短路的区别 →——MST 关心「连通所有点的总代价最小」，最短路关心「两点间路径最短」——两者都用 greedy + 优先队列，但目标不同，常被混淆。
近似 TSP——绕 MST 走一圈（再抄近路跳过重复点），能得到度量空间旅行商问题的 2-近似解——物流排线的快速可行解。
回到本页 Prim / Kruskal 看这棵树是怎么一条边一条边长出来的——上面的「最省网络」正是 Prim / Kruskal 运行得到的结果。
5 · 它真实跑在哪里
网络与基建设计：用最短的总线缆 / 管道 / 电网把所有节点连通（MST 的字面应用）、数据中心或传感器集群的最省通信骨干。
聚类与图像分割：single-linkage 层次聚类等价于在 MST 上由大到小切边；经典图像分割算法 Felzenszwalb-Huttenlocher 直接建在 MST 上。
近似算法:MST 给出度量空间 TSP 的 2-近似解（绕树一圈再抄近路）；也用于电路布线、最小代价相似度骨架。
底层零件:Kruskal 里的 **union-find（并查集）**本身就是连通性合并、账号 / 好友关系归并、离线连通查询的常用结构——它的来龙去脉（quick-find → quick-union → weighted → 路径压缩）单独成系列：并查集 · Union-Find。