[数据结构与算法]生成树与最小生成树

一、树

包含N个顶点的无向图G称为一棵树，它满足以下任意一个条件：
（1）图G是连通的并且有N-1条边。
（2）图G是连通的并且不包含圈。
（3）图G不包含圈并且有N-1条边。
（4）图G中任意两个顶点之间有且只有一条路径。
（5）图G中任意一条边都是桥，即去掉图G中的任意一条边都会使图变得不连通。

上图中第一颗树是自由树，因为很难看出树根。通过把某个顶点设定为根，就可以得到树的层次表示，称为根数，如第二颗树所示。

二、广度优先搜索算法

以上图为例，利用广度优先搜索算法寻找该图的包含某个顶点(例如顶点1)的连通片可以描述如下：
（1）以顶点1为初始顶点,这个顶点记为第L${}_0$层；
（2）第一步是找到顶点1的所有邻居顶点，包括顶点2和3，把这两个顶点记为第L${}_1$层；

（3）第二步是找到第L${}_1$层顶点的所有未在前面层中出现的邻居,包括顶点4、5、7和8,把这4个顶点记为第L${}_2$层；

（4）第三步是找到第L${}_2$层顶点的所有未在前面层中出现的邻居，包括项点6,把这一顶点记为第L${}_3$层；

（5）已经找不到第L${}_3$层顶点的所有未在前面层中出现的邻居,算法终止。此时得到一个以顶点1为根的树，包括上图中的顶点及实线边，称为广度优先搜索树。如果把这些顶点之间原有的边(上图中的虚线边)添加进来,就得到包含顶点1的连通片。
如果要找出一个图中的所有的连通片，那么可采用如下方法：先选取该图中的一个顶点x，用广度优先搜索得到包含顶点x的连通片；再选取一个不包含在该连通片中的顶点Y,用广度优先搜索得到包含顶点Y的连通片;如此下去,直至所得到的这些连通片包含了图中所有的顶点。

三、最小生成树

1、定义

如果一个连通图本身不是树，那么该图也可以看做是在一个树 的基础上添加一些边而形成的，这就是生成树的概念。
一个顶点数目很大的图，其生成树的数目一般而言可能大得惊人。例如，一个顶点标志了标号的完全图K${}_N$的生成树个数${}_T$(K${}_N$)有如下的Caylay公式:
${}_T$(K${}_N$)=N${}^{N?2}$。
下图为包含5个顶点的连通图及4个生成树。

将生成树的概念推广到加权无向图，此时每个生成树边数虽然相同，但边的权值不同。权值之和最小的生成树称为最小生成树。
注意：最小生成树可能不唯一。但是当一个连通图中所有边的权值都不相同时最小生成树是唯一的。

2、两个定理

定理1：连通图的一个权值之和最小的一个连通子图一定是连通图的一个最小生成树。
定理2：给定连通图G=(V,E,W)并假设所有边的权值互不相同,则有：
（1）最小生成树的割性质:令S是图G的任意顶点子集,S≠0(空集),S≠V。令边e是一个端点在S中,另一端点在V-S中的最小权值边。那么图G的最小生成树必然包含边e。
（2）最小生成树的圈性质:令C是图G中的一个圈，并假设边e是圈C中权值最大的一条边，那么图G的最小生成树必然不包含边e。

3、构造最小生成树

构造最小生成树有两个经典的算法，Prim算法和Kruskal算法。这两个算法在数据结构中很经典，这里不在讲述。