最小生成树（

经验分享区
1

正在复盘的时候发现还没有发过MST的总结帖

最小生成树（Minimum Spanning Tree, MST）是连接无向图所有顶点且边权和最小的生成树。（生成树必须覆盖原图的所有顶点，不然那个叫生成森林）

  • 连通性：任意两个顶点之间都能互相到达
  • 无环性：生成树中没有环
  • 边数为 n−1：对于 n 个顶点的图，生成树恰好有 n−1 条边
  • 边权和最小：在所有可能的生成树中，最小生成树的边权之和最小

核心性质

1. 唯一性
对于边权互不相同的无向图，最小生成树是唯一的。如果存在两棵不同的MST，取一条在其中一棵树中但不在另一棵树中的边，替换后会导致总权值增加或减少，从而矛盾
2. 割性质
对于图G的任意割（将顶点集V划分为S和V-S），如果边e是跨越该割的最小权边，则每一棵MST都包含边e。
3. 环性质
在图中任意环中，权值最大的边不会出现在MST中。若将环中最大边加入生成树，会形成环，违反无环性，因此MST中不会包含该边

目前比较强势主流的寻找MST的做法主要是

Kruskal算法：按边权从小到大加入边，使用并查集判断是否形成环，保证每步选择的边是安全边

Prim算法：从某一节点开始生长，每次选择连接已选节点集合与未选节点集合的最小权边，保证局部最优累积为全局最优

先讲一下关于kruskal的事（下文中默认边数为m，点数为n）

关于做法

加入边按权值大小进行排序

遍历判断当前边的端点是否在一个并查集内，不在就进行合并（也就是把边加进去）

关于时间复杂度

加入边进行排序 O(m log m)

遍历忽略不计

加入忽略不计

并查集忽略不计

就是 O(m log m)

还算是一个比较常用的算法，但我感觉已经被它欺骗很多次了

可以选择不看的东西

image
image1176×799 107 KB

就这个，我当时差点把正解都想到了

最小生成树+子集枚举

因为不知道往图内加边不会影响原本就不在图内的边

80(我应该也想不到归并)->32->8(自作聪明加了个剪枝欸嘿:winking_face_with_tongue:)

然后是prim

prim好啊

以前还天天把kruskal当成宝

现在感觉就是区

具体做法就是先将一个点设为特殊状态

考虑加入所有与特殊点可能相连的普通节点，每次取出距离最小的点固定为特殊节点

循环往复，暴力也有 O(n^2 + m) ，因为一般而言， m≤n(n-1)/2 ，所以我可以理解为在极限数据下，prim可以薄纱kruskal吗

对以前一道题印象深刻

就是n个点，每个点有权值 a_i ， 连接 i 和 j 两点的代价为 (a_i + a_j) \bmod m

然后就是固定 i ,寻找 j ,可以做到 O(n \log n + m) 的（可以优化一下的，这么说，是prim赢了）

1 个赞