生成树算法

图论名词

在图论的数学领域中，如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

自由树

自由树就是一个无回路的连通图（没有确定根）(在自由树中选定一顶点做根，则成为一棵通常的树)。从根开始，为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序，则它就成为一棵有序树。在图的应用中，我们常常需要求给定图的一个子图，使该子图是一棵树。

生成树

在图论中，如果连通图的一个子图是一棵包含的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树是连通图的包含图中的所有顶点的极小连通子图。

图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

通用定义：

若从图的某顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。

（1）若G是强连通的有向图，则从其中任一顶点v出发，都可以访问遍G中的所有顶点，从而得到以v为根的生成树。

（2）若G是有根的有向图，设根为v，则从根v出发可以完成对G的遍历，得到G的以v为根的生成树。

（3）若G是非连通的无向图，则要若干次从外部调用DFS(或BFS)算法，才能完成对G的遍历。每一次外部调用，只能访问到G的一个连通分量的顶点集，这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树。G的各个连通分量的DFS(或BFS)生成树组成了G的DFS(或BFS)生成森林。

（4）若G是非强连通的有向图，且源点又不是有向图的根，则遍历时一般也只能得到该有向图的生成森林。

分类

1）生成树的求解方法

设图是一个具有n个顶点的连通图。则从G的任一顶点（源点）出发，作一次深度优先搜索（广度优先搜索），搜索到的n个顶点和搜索过程中从一个已访问过的顶点搜索到一个未曾访问过的邻接点，所经过的边（共n-1条）组成的极小连通子图就是生成树。（源点是生成树的根）

通常，由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。

注意：

①图的广度优先生成树的树高不会超过该图其它生成树的高度

②图的生成树不惟一，从不同的顶点出发进行遍历，可以得到不同的生成树。

最小生成树

对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：

其中，TE表示T的边集，w(u，v)表示边(u，v)的权。权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。

普里姆(PRIM)算法

算法简单描述

1）输入：一个加权连通图，其中顶点集合为V，边集合为E；

2）初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {}，为空；

3）重复下列操作，直到Vnew= V：

a. 在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b. 将v加入集合Vnew中，将边加入集合Enew中；

4）输出：使用集合Vnew和Enew来描述所得到的最小生成树。

伪代码描述

克鲁斯卡尔(Kruskal) 算法

Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。

算法流程：

输入：图G

输出：图G的最小生成树

具体流程：

1）将图G看做一个森林，每个顶点为一棵独立的树

2）将所有的边加入集合S，即一开始S=E

3）从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'

4）重复(3)直到所有点属于同一棵树，边集E'就是一棵最小生成树

时间复杂度：

Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这一步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。

应用

网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省