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