### 最小生成树及其拓展知识点解析
#### 一、最小生成树定义与基本概念
- **定义**：在一个加权无向图中，一个生成树是指包含图中所有顶点的树，且任意两个顶点间都恰好有一条路径相连。最小生成树（Minimum Spanning Tree, MST）是在所有生成树中总边权重最小的那个生成树。
#### 二、最小生成树构建算法
- **Kruskal算法**：
- **时间复杂度**：\(O(m\log m)\)
- **原理**：按照边的权重从小到大排序，依次考虑每条边，如果这条边的两端不属于同一个连通分量，则添加此边，直至所有顶点构成一个连通分量为止。
- **Prim算法**：
- **时间复杂度**：通常为\(O(n^2)\)或\(O(m\log n)\)使用优先队列优化
- **原理**：从任意顶点开始，每次都选择距离当前已形成的生成树最近的顶点加入，直到所有顶点都被包含在内。
#### 三、最小生成树的基础性质
- **切割性质**：
- **描述**：若图G的所有边权值都不相同，设点集S是既非空集也非全集的点集V的子集，边e是满足顶点分别在S和V-S集合中的所有边中权值最小的一个，则V中的所有生成树均包含e。
- **证明**：设\( <u,v> \)是连接S和V-S集合所有边权最短的边。若存在生成树不包含\( <u,v> \)，连接\( <u,v> \)，形成一个环，环上至少有一条不是\( <u,v> \)的边能够连接集合V和S-V，其权值比\( <u,v> \)大，用\( <u,v> \)替换后，MST变小，矛盾！因此所有生成树均有\( <u,v> \)边。简单概括就是：连接两个集合的边权最小的边必被所有生成树包含。
- **回路性质**：
- **描述**：若所有边权值都不相同，设C是G中的任意回路，边e是C上权值最大的边，则G中所有生成树均不包含e。
- **证明**：若存在生成树包含C环上的最大权值边\( <u,v> \)，删除\( <u,v> \)后，变成两个连通块S和T，C环上u->v不经过\( <u,v> \)边的路径中至少有一条边横跨S和T连通块，用该边替换\( <u,v> \)后，生成树变小，矛盾！因此所有生成树均没有边\( <u,v> \)。简单概括就是：任意回路上的边权最大的边必定不被生成树包含。
#### 四、最小生成树的拓展问题
- **增量最小生成树问题**：
- **问题描述**：在N个点的空图上依次加入M条带权边，求每加入一条后的MST权值。
- **解法1**：每生成一个MST就把没有选的边删掉，加入一条新边就做一次(N-1)+1=N条边的Kruskal算法，时间复杂度为\(O(mn\log n)\)。
- **解法2**：我们发现，加入一条边e=(u,v)后，图中恰好包含一个回路，(u,v)在这个回路中。根据回路性质，删除该回路上权值最大的边即可。只需在加边之前的MST上用DFS找到u到v的唯一路径上权值最大的边，再和e比较，删除较大者即可。时间复杂度为\(O(mn)\)。
- **最小瓶颈生成树问题**：
- **问题描述**：给出加权无向图，求一棵生成树，使最大边权值尽量小。
- **解法**：由于只关心最大边权值，我们可以从一个空图开始，将边按照权值从小到大依次加入，当图第一次联通时，那棵生成树就是答案。这实际上是Kruskal算法，即原图的最小生成树就是一棵最小瓶颈生成树。
- **最小瓶颈路问题**：
- **问题描述**：给出加权无向图的两个结点u和v，求出从u到v的一条路径，使得路径上权值最大的边的权值尽量小。
- **解法1**：二分+BFS，二分最大边的权值，BFS跑一遍看这样的最大边权是否可以找到一条从u到v的路径，时间复杂度为\(O(\log d*m)\)，其中d表示最大的边权的最大值。
- **解法2**：可以像求“最小瓶颈生成树”一样思考，最小瓶颈路便是最小生成树上的对应路径。
- **次小生成树问题**：
- **问题描述**：求权值之和第二小的生成树的权值和。
- **解法1**：枚举MST中不在次小生成树中出现的边(n-1次)，每次在剩下的边里求一次MST，时间复杂度为\(O(nm\log m)\)。
- **解法2**：预备结论：次小生成树一定可由MST更换一条边得到。证明让我们换种方式去看待这个结论（一个生成树可以通过换边得到另一个生成树），T是某一棵最小生成树，T0是任一棵异于T的生成树，通过变换T0->T1->T2->...->Tn(T)变成最小生成树。所谓的变换是，每次从T(i-1)到Ti的过程就是替换了一条边，使得Ti更接近最小生成树T。
以上内容详细介绍了最小生成树的基本概念、构建算法、基础性质以及相关的拓展问题。通过对这些知识点的学习，可以更深入地理解最小生成树的概念及应用，并掌握解决最小生成树及其相关问题的方法和技术。
