图论02.最小生成树_学习笔记+模板 - 副本

一、定义与性质 ● 需要的前导知识点

• 生成子图
• 生成树

● 性质

我们定义无向连通图的 最小生成树 （Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

二、最小生成树算法与模板 1.Kruskal 算法

• Kruskal算法是一种常见而且好写的最小生成树算法，本质属于贪心算法；
• 基本思想：从小到大加入边
• 适用于稀松图，稠密图应该用Prim算法
• 需要前导知识：并查集、贪心算法、图的储存方式
• 如果使用 O ( m log ⁡ m ) O(m\log m) O(mlogm) 的排序算法，并且使用 O ( m α ( m , n ) ) O(m\alpha(m, n)) O(mα(m,n)) 或 O ( m log ⁡ n ) O(m\log n) O(mlogn) 的并查集，就可以得到时间复杂度为 O ( m log ⁡ m ) O(m\log m) O(mlogm) 的 Kruskal 算法。

● 算法的实现

伪代码实现 1 Input.   The edges of the graph  e ,  where each element in  e  is  ( u , v , w )  denoting that there is an edge between  u  and  v  weighted  w . 2 Output.   The edges of the MST of the input graph . 3 Method.   4 r e s u l t ← ∅ 5 sort  e  into nondecreasing order by weight  w 6 for  each  ( u , v , w )  in the sorted  e 7 if   u  and  v  are not connected in the union-find set  8 connect  u  and  v  in the union-find set 9 r e s u l t ← r e s u l t    ⋃   { ( u , v , w ) } 10 return   r e s u l t \begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v, w) \\ & \text{ denoting that there is an edge between } u \text{ and } v \text{ weighted } w . \\ 2 & \textbf{Output. } \text{The edges of the MST of the input graph}.\\ 3 & \textbf{Method. } \\ 4 & result \gets \varnothing \\ 5 & \text{sort } e \text{ into nondecreasing order by weight } w \\ 6 & \textbf{for} \text{ each } (u, v, w) \text{ in the sorted } e \\ 7 & \qquad \textbf{if } u \text{ and } v \text{ are not connected in the union-find set } \\ 8 & \qquad\qquad \text{connect } u \text{ and } v \text{ in the union-find set} \\ 9 & \qquad\qquad result \gets result\;\bigcup\ \{(u, v, w)\} \\ 10 & \textbf{return } result \end{array} 12345678910​Input. The edges of the graph e, where each element in e is (u,v,w) denoting that there is an edge between u and v weighted w.Output. The edges of the MST of the input graph.Method. result←∅sort e into nondecreasing order by weight wfor each (u,v,w) in the sorted eif u and v are not connected in the union-find set connect u and v in the union-find setresult←result⋃ {(u,v,w)}return result​ 算法核心思想

简而言之，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。

其中，查询两点是否连通和连接两点可以使用并查集维护。

证明

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n − 1 n-1 n−1 条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 F F F，令 T T T 为这棵 MST，考虑下一条加入的边 e e e。

如果 e e e 属于 T T T，那么成立。

否则， T + e T+e T+e 一定存在一个环，考虑这个环上不属于 F F F 的另一条边 f f f（一定只有一条）。

首先， f f f 的权值一定不会比 e e e 小，不然 f f f 会在 e e e 之前被选取。

然后， f f f 的权值一定不会比 e e e 大，不然 T + e − f T+e-f T+e−f 就是一棵比 T T T 还优的生成树了。

所以， T + e − f T+e-f T+e−f 包含了 F F F，并且也是一棵最小生成树，归纳成立。

实现过程

将边按照从小到大排列,依次加入最小边,如果加入这条边不形成回路(使用并查集,不在同一个集合的两个顶点就不会形成回路),就加入这条边,直到加入n-1条边为止.

#define MAXV 100//后面都会用到
#define MAXSIZE (100*100)
#define INF 100000//INF表示正无穷
struct MGraph
{
    int edges[MAXV][MAXV];//邻接矩阵的边数组
    int n;//顶点数,弧度;
};
MGraph g;
int sum;
//并查集
int Father[MAXV]; // Father[i] 表示 i 的父节点
int FindSet(int x)
{
    while (x != Father[x]) x = Father[x];
    return x;
}
//边
struct Edge
{
    int p1,p2;
    int val;
};
bool cmp(Edge a,Edge b)
{
    return a.val