最小生成树_详解(C++描述、Python描述)

⚪ 本文内容基于C++和Python讲解最小生成树相关的知识以及相关的算法 ⚪ 本文原创，转载请联系作者，并注明出处 ⚪ 由于作者水平有限，可能内容存在谬误，欢迎读者批评指正 一、关于树的定义

本定义适用于有根树和无根树

• 森林（forest）：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。
• 生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 n − 1 n - 1 n−1 条，将所有顶点连通。
• 结点的深度（depth）：到根结点的路径上的边数。
• 树的高度（height）：所有结点的深度的最大值。
• 无根树的叶结点（leaf node）：度数不超过 1 1 1 的结点。
• 有根树的叶结点（leaf node）：没有子结点的结点。

以下定义适用于有根树

• 父亲（parent node）：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。 根结点没有父结点。
• 祖先（ancestor）：一个结点到根结点的路径上，除了它本身外的结点。 根结点的祖先集合为空。
• 子结点（child node）：如果 u u u 是 v v v 的父亲，那么 v v v 是 u u u 的子结点。 子结点的顺序一般不加以区分，二叉树是一个例外。
• 兄弟（sibling）：同一个父亲的多个子结点互为兄弟。
• 后代（descendant）：子结点和子结点的后代。 或者理解成：如果 u u u 是 v v v 的祖先，那么 v v v 是 u u u 的后代。
• 子树（subtree）：删掉与父亲相连的边后，该结点所在的子图。

在本专题中，我们重点讨论有根树中的生成树 二、生成树、生成森林的定义 1.生成树

什么是生成树？

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树我们通过距离来直观的展示生成树的含义。

如下图是一张包含5个结点、5条边的无向图 A A A：

我们对这张图进行遍历，根据定义，我们可以得知连通图的生成树必须满足下列两个条件：

1. 包含连通图的所有的节点
2. 任意两顶点间有且仅有一条通路

由于连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。因此对于本图我们可以得到两颗不同的生成树:

我们定义生成树的权为生成树中所有边权的求和，图中 M S T − A MST-A MST−A的权值为 Q A = L 2 + L 3 + L 4 + L 5 Q_A = L2 + L3 + L4 + L5 QA​=L2+L3+L4+L5， M S T − B MST-B MST−B的权值为 Q B = L 1 + L 3 + L 4 + L 5 Q_B = L1 + L3 + L4 + L5 QB​=L1+L3+L4+L5

不妨设 Q A > Q B Q_A > Q_B QA​>QB​，如果我们想要得到一棵连通所有节点且边权和最小的生成树，显然 Q B Q_B QB​符合要求，我们称 Q B Q_B QB​为图 A A A的最小生成树。

**Attention！**只有连通图才有生成树，才有最小生成树。而对于非连通图，只存在生成森林。

我们再举一个复杂的图的例子：

本图的最小生成树如右图标红所示。

最小生成树有什么用？

我们举一个现实生活中鲜明生动的例子：修煤气管道(仅仅作示例，实际可能并非如此)

我们拥有一个城镇，城镇的房子之间或有通路，或无通路，现在我们需要修一条煤气管道，由于煤气管道造假高昂，所以要求给出一个方案，保证管道经过每一家每一户而代价最小。经过了对最小生成树的学习，我们不难发现：最优方案便是地图路径连通图的最小生成树。

2.生成森林

生成树是对应连通图而言，而生成森林是对应非连通图而言。

我们知道，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。

我们给出一张非连通图 B B B，其对应的一种生成森林如右所示：

三、最小生成树算法详解(C++描述、Python描述)

我们在讲解的过程中对于图的储存结构全部采用边集的方式进行储存

1.Kruskal’S Algorithm 1.1 核心思想概述

具体的概括：维护一个森林，查询两个结点是否在同一棵树中，并连接两棵树。

反应到算法上的具体体现：维护一堆集合，查询两个元素是否属于同一集合，合并两个集合。

由于涉及到的集合的查询问题，我们可以采用并查集对查询过程进行优化。

1.2 详解

我们继续使用下面这张示例图来讲解Kruskal算法的原理及过程。

我们首先建图，读入边权信息；然后我们对边集按照边权从大到小的顺序进行排序，得到一个有序的边集数组。我们将每个点视为一个独立的连通分量，遍历边集，每次遍历查询两个结点是否位于同一连通分量中(不成环)，对两点选择性进行连接。

我们不难发现，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​ 具体的执行过程图解：

1.3 C++描述：Kruskal’s Algorithm

#include 
#define rnt register int
#define ll long long
using namespace std;
const int N = 2005, M = 1000000;
const int inf = 0x7fffffff;

//定义边结构
typedef struct edge{ int u, v, dis; }edge;

int n, tot = 0;
int px[N], py[N], father[N];
edge edgeset[M];

//定义比较器
inline bool cmp(const edge &a, const edge &b){ return a.dis > b.dis; }

//并查集模板
int get(int x){
    if(father[x] != x) father[x] = get(father[x]);
    return father[x];
}

void kruskal(){
    int u, v, dis, cnt = 0, sum = 0;
    for(rnt i = 1; i