📌 📄 内容摘要:
langmouren 在 Kruskal 重构树 中发帖
自己以前学过一些 OI，初来 L 站，发现有一个算法标签，遂试图把一些文章发出来水点经验之类的。
应该是无人在意的，写的也很浅略，如果发这类东西违反了某个我没有注意到的站规请告诉我……
Kruskal 重构树
说实话，这个东西还是过于冷门了，感觉刷题练这个真心没啥用。
2025年10月：我承认我以前说话太大声了，连着几次考试都能用这个。
什么是 Kruskal 重构树
对于一张无向图，我们可以通过 Kruskal 算法求出其最小/最大生成树。
在求最小/最大生成树的时候，设两点 x、y 连边，则新建一个节点 p，连接到 x、y，将 p 的权值设为原边的权值。即用一个点替换了原本应该连接的边。
这是原图：
[图片]
找到它的最小生成树：
[图片]
按边权从小到大建立 Kruskal 重构树：
[图片]
[图片]
[图片]
[图片]
Kruskal 重构树的性质
...
────────── 链接信息 ──────────
🔗 论坛链接: linux.do
📎 访问地址: https://linux.do/t/topic/1443443/1
─────────────────────────────
📢 来源：LINUX DO
