讲解（上）在线视频

这一节，我们来学习最小生成树

首先，我们来看几个概念

第一个，连通图

对于无向图来说

如果顶点v到顶点w

有路径，则称v和w是连通的，两个顶点是连通的

也就是说

从一个顶点能走到另外一个顶点

若任意两个顶点都是连通的

则称图是连通图

注意，是任意两个顶点之间都有路径

对于有向图来说

若顶点v到w以及w到v都有路径

则称v和w是连通的

因为，有向图中，两个顶点之间的边是带方向的

要相互都能走到、都有路径

才说这两个顶点是连通的

若任意两个顶点都是连通的

则称这时候的有向图为强连通图

所以，强连通图

就是连通的有向图

n个顶点的连通图，至少有n-1条边

但反过来不成立

n个顶点的连通图

至少有n-1条边

这个如何来证明呢

其实

我们把一棵树当做图的特例

树中n个顶点，是有n-1条边的

那么，你在树当中，任意删掉一条边

因为，树当中任意两个顶点之间的路径，是唯一的

假设不经历重复的顶点

你现在删掉一条边，那这条边所依附的两个顶点，肯定就到达不了了

所以，这时候的图就变成了一个非连通图

但反过来，有n-1条边的图，是不是就是连通图呢

这个很明显

不一定

我们再来看第二个概念

连通分量

连通分量，是指图的最大连通子图

连通分量是图的一个子图

而且是最大连通子图，什么意思呢

这里的最大，是指顶点个数达到最多

也就是，如果再在子图当中，任意增加一个顶点

这时候的图，会变成非连通图

也就是，顶点个数不能再多了

再多，就变成非连通图了

这时候的图，就叫做最大连通子图

比如，我们给出这样一个图

这个图

它很明显不是连通图

因为，有一些顶点和另外一些顶点之间，是没有路径的

但是，它是由两个连通分量构成的

也就是说

这两个，是原来的图的最大连通子图

你在这两个图当中，任意加上其它的顶点

比如这个图

你去加上3、5、6

这三个顶点当中任意一个顶点，图就变成了非连通图

这个也是一样的

你加上1、2、4三个顶点当中的任意一个顶点，也变成了非连通图

所以，这两个子图是最大的连通子图

下一个概念，生成树，生成树

是指连通图的最小连通子图

注意，生成树的概念，是对连通图而言的

因为，生成树要包含图当中所有的顶点

如果给出来的一个图，并不是连通图

那就没有生成树的概念了

因为，生成树当中，每两个顶点之间都是有路径的

只有对于连通图来说，才有生成树的概念

那这里的最小，又是什么意思呢

最小，是指边的条数达到最少

跟刚才连通分量不一样

这里的最小连通子图，表示的是边的条数达到最少

不能再少了

如果再少，图就变成了非连通图

我们可以知道，n个顶点的生成树一定有n-1条边

刚才已经说过了

因为，树的n个顶点一定有n-1条边

比如，上面这个图

它是一个连通图

我们可以画出它的几棵生成树

4个顶点有3条边，就可以保证4个顶点是连通的

我们给出了3棵不同的生成树

它们都是最小连通子图

比如，我们在第二棵树当中，任意删掉一条边

比如，把这条边删掉

那么，0和3这两个顶点

它们就不是连通的了

这张图就变成了一个非连通图

所以

生成树是有n-1条边的

如果多了，将出现环

因为，生成树已经是连通图了

任意在两个顶点之间加一条边

比如，我在1和2之间加一条边

那么，没加这条边之前

1、2这两个顶点也是可达的

经历的路径是1、0、2，现在，你直接在1、2之间加了条边

那说明1、2之间有多条路径

必然构成一个环

如果边数少于n-1

那么，将变成非连通图

因为，树当中，你任意删掉一条边

这两个顶点，肯定就不连通了

必然会变成非连通图

我们再来看第四个概念

DFS和BFS生成树

我们前面讲深度优先和广度优先遍历(搜索)的时候，实际上，会走图当中的n-1条边

我们记录下这n-1条边

并且，把它们作为生成树的边

这时候的生成树，就叫做深度优先搜索以及广度优先搜索生成树

比如，我们看这个图

我们先对它进行深度优先搜索

绿色的边，是表示我们走过的边，红色的边

表示没有走过的边，n个顶点

我们只需要经历

n-1条边

所以，就构成了一个

深度优先生成树

当然

为了让它看起来像树的样子

我们可以扭曲一下、旋转一下绿色的边

再看它的广度优先生成树，同样，绿色的边表示走过的边，红色的表示没走过的

讲了生成树之后

我们再来看最小生成树

简称MST

最小生成树

是表示连通网的所有生成树中，边的权值之和最小的生成树，比如，给定这样一个包含6个顶点、10条边的图

现在，只需要在10条边当中，选出5条

就能让这6个顶点任意两个顶点之间是可达的

也就是，让它变成一个最小的连通子图

选哪5条边呢？我们现在给出了它的一棵最小生成树

这5条边

如何来选呢

除了这样一棵生成树之外

是否还有其他边的权值之和，也是最小的生成树呢

需要注意，最小生成树可能不唯一

比如，我们将这10条边的权值全都认为是1

很显然

选5条边的选法就有很多

所以，最小生成树可能不唯一

我们即将介绍两种产生最小生成树的方法

分别是普里姆算法，和克鲁斯卡尔算法

这两种算法，都基于一个相同的性质

叫做MST性质

接下来，我们就看看这个性质

先有几个已知条件，给出了图G

顶点集合、边的集合都给你了

然后，有一个集合是U

它是一个顶点的集合，是给定的图的顶点集合的子集

如果有一条边，这条边的权值是最小的

而且，这条边依附的两个顶点

一个来自于U，一个不来自于U

也就是，一条边(u、v两个顶点之间的边)，u来自于U集合

而v不来自于U集合

现在，MST性质是什么呢

就是，一定有一棵最小生成树是包含(u,v)这条边的

如何证明这个性质呢

我们用反证法，我们证明，没有任何一棵最小生成树

包含(u,v)这条边，或者说，(u,v)这条边不属于任何一棵最小生成树

我们来看

红色的顶点，是属于U集合的

蓝色的顶点

是属于V-U集合的，或者说，蓝色的顶点不属于U

这个集合

现在，我们给出一棵最小生成树T

这棵最小生成树T

是经历v'和u'这两个顶点之间的边，来连接U和非U这两个集合

换句话说

我们不是通过v和u这两个顶点之间的边，来连接蓝色的顶点集合和红色的顶点集合

因为，根据最小生成树(的性质)，任意两个顶点之间都有路径

那么，一定有一条边，将U集合里面的顶点和不属于U集合里面的顶点，把它们连接起来

假设，这条边是u'和v'

之间的这条边，也就是红色的这条边，T既然是一棵最小生成树

如果我们把红色的边，把它换成绿色的边

也就是(v,u)这条边

现在，新的这棵树

它的权值之和，一定是小于(或等于)T的

因为，绿色的边的权值是最小的

它小于(或等于)红色的虚线这条边

而且这时候，v、u之间的路径是v直接到u

而不是v经过v'(或其他顶点)到u

我们现在通过绿色的边，也能将U集合和非U集合里面的顶点连接起来

现在，T'它的权值之和小于(或等于)T，而T都是一棵最小生成树了

这是我们假设的，那T'也应该是一棵最小生成树

但是，跟我们前面的假设是冲突的

我们说，依附u、v的边

不属于任何的最小生成树

现在，T'却是一棵最小生成树

它包含(u,v)这条边

所以冲突，我们也就证明了这个性质