这一讲我们来介绍最小生成树的第一个算法,prime算法。 这个算法的设计思想呢, 它是这样来描述的,它的输入是一个图, 带权图,这是它的结点标号是1到n。 它的输出是这个图的最小生成树T。 我们看它的设计思想,初始,这个S集合 是1号结点,把它放到这个集合里面。然后我们逐渐地 把结点往这个S集合里挑,在挑的时候, 就把这个结点所关联的边就放到树中去,挑的原则是什么呢? 选择连接S与V-S集合的最短边,就是 S集合里,现在只有一个结点,初始,其他的结点都在V-S集合里边。 那么连接这两个集合里有很多条边,把那个权值最小的 那条最短边e,把它挑进去,挑的时候, 它一个结点i在S里头,另外一个结点j,这V-S里头, 因此把这棵树的边e加到树里去以后,那么, j这个结点也就同时放到S集合里面去,所以不断地扩张这个S集合, 每挑进一个结点就带着一条边进去,啊,它是这样的做法。 继续这个过程直到S集合, 包含了图中的全部结点为止。这是它的设计思想。 下面我们看一下伪码。这是伪码,初始,S只有1号结点, 那么当V-S不空的时候,就是还有结点没有进到S集合中的情况下, 就要从这里边挑结点。选什么结点呢?选的是j号节点。 j满足什么条件呢?就是它到S中某个顶点的这个权值 是所有连接V-S和S那些边的权值里最小的。 这样就把这个j号顶点就挑到S集合里去了。那么不断地这样挑, 到S集合里包含了全部顶点,算法就结束了。下面我们看一个例子。 这是原始的这个图j,下边开始的S集合, 只有1号顶点,先进入S集合, 那么这个就是S集合,剩下这些个顶点 就在V-S集合里头。现在连接S集合和V-S集合的顶点的边 就是这三条边。这三条边里边权值最小的边是这条边, 所以下边就把3号顶点 加到S集合里边去,而这条边就变成了树的边了。 这样就变成了S集合成两个顶点了。那么连接这个S集合 和这蓝色的是V-S集合顶点,连接, 这种黄色顶点和蓝色顶点的最短边是哪条边呢? 我们看到是这个,就是长度是4的边。 那么下边就把这条边挑到树里去。 同时把这个结点6就进入了S集合。 到这一步以后S集合已经含有三个顶点了,这个蓝颜色的是 V-S集合里面,下一步再挑连接这两个集合的最短边, 应该是这个2,长度是2的边。把4号顶点就进了S集合了。 那么再下一步连接S集合和V-S的最短边,应该是 这条边。所以, 2号顶点就进了S集合了,这条边也进了树边了。 最后就是剩下这个顶点, 那么它带的边就是这个3号边。因此我们就可以得到 这颗最小的生成树。它是把刚才讲的这些个边 都把它加到树里边去了。 下面我们来对这个算法 正确性来进行证明,用的还是归纳法。 首先我们先叙述一个命题,对于任何的k小于n 存在着一颗最小的生成树,包含了算法前k步选择的边, 那么当k表示任意的自然数, 不超过n的自然数,如果这个命题对于任意的k都是正确的话, 那说明算法的每一步都是正确的,它最终得到的结果也是正确的。 下边我们看看归纳基础,归纳基础是k等于1, 一定存在着一颗最小的生成树,它选择了 连接1号结点的那个最短边,因为算法第一步 选择就是连接1号结点的那个最短边。 这是归纳基础要证明这个结论。 接着还需要证明的是归纳步骤。假设算法前k步选择的边, 它能够构成一棵最小生成树的边,那么算法前k+1步 选择的边也会构成一颗最小生成树这边。 所以要把这个归纳步骤证明了以后这个归纳法就完成了。 下边我们先考虑这个归纳基础。 归纳基础说的是存在一颗最小的生成树,包含了算法第一步 选择的边,就是连接1号结点的那个最小权的边, 比如说这条边是{1,i}。我们从一棵 最小生成树出发,T,假定T不包含着{1,i}边, 怎么办呢?按照我们刚才讲的改到这棵树的方法, 我们把{1,i}这条边并到这棵树上去, 这样这棵树就还有了一个回路, 回路中关联着1的,一定会有另外一条边是{1,j}, 然后我们用{1,i}边来替换{1,j}边,得到的数 是T'。我们可以证明T' 它也是生成树,而且它的权值比T 要小于等于T的权值。那这就是假定这是原来 一颗最小的生成树, 它可能不包含着{1,i}这个边,这个边是连接着1的 所有边里最短的那条边。按照刚才讲的这个方法,它就是把这个{1,i}加上, 就形成一个回路,回路以后然后把这条边去掉, 所以经过改造以后它就这样连同起来了。 相当于我们用{1,i}边替换了原来树中的{1,j}边。 根据算法的步骤,它第一步挑的是连接1的权值最小的边, 所以{1,i}边的权值比{1,j}边的权值要小,因此这棵树的权值, 跟这棵树的权值来比较的话,我们用一条小的权值 替换这条大的权值,因此这个树的权值 会更小,也就是说,W(T')小于等于W(T)。 它的权值不超过原来的权值。 那么如果原来是一棵最优的话,那这棵树也是最优的。 而且它包含了算法第一步选择的边。 所以归纳基础是正确的。下面考虑归纳步骤。 归纳步骤的做法呐就是算法进行了前K步, 已经选择了k条边进这个树,就是e1,e2 到ek,这些个边的端点构成了集合S。 根据归纳假设一定存在着一颗最小的生成树,包含了这k条边。 那就是说像这个情况, 这是算法,它, K步选择的顶点都进了这个集合里面, 而它第n也都 进入到树里边,这个时候算法下一步选择的是 ek+1这条边,按照算法来挑。 它是连接S集合,底下V-S集合所有连接的 这些边里边,这是一个权最小的边,算法下一步挑它。 那么这个情况下, 如果这条边本身就在这棵T树里面,因为根据这个归纳假设, 存在着T这样一棵最小生成树,包含了原来选择那些结点和所有的边在内, 同时,它也包含了这条边就是假定这条边 也在这棵T树里面,那这颗T树本身就是包含了算法, 前K+1步选择的一棵最小生成树。显然这个归纳步骤就证出来了。 那么下面我们就考虑假定这条边就是连接S和V-S最短的边 不在这棵T树里面会是什么情况?如果这棵T树不含有这个边, 怎么办呢?我们就把这个边, 就是原来那个T树是这样一个结构,它并不含有算法下一步选择的这条边 就是ek+1在内,我们就把这条边加到这棵树上去, 那就会形成一个回路,形成回路呢,那么这个回路连接 S跟V-S的另外一条边就是e这条边, 下面我们就把e这条边去掉, 按照刚才的那个树的性质这就又恢复成了一棵新的树,这棵树叫 T*,这棵树相当于用算法第K+1步的边, T*,这棵树相当于用算法第K+1步的边。 这样替换了以后这棵新的树T*比那个T的权值 会有什么变化呢?我们可以看到,这个T*这样替换了以后, 它的权值比原来T的权值要小, 因为什么呢?因为这条边的权值比刚才拿掉那条e边的权值要小。 这个根据是算法的选择是我在所有连接S跟V-S的边中, 选的是权值最小的边,所以这条边一定比e的权值要小。这样 当你用这条边ek+1替换了e以后,得到了这个T*这棵树的权值 一定比原来那棵树的权值还要小,所以如果这个是一个 最优树的话,我新做的这棵树的权值不比它 的权大。因此T*也是最优的。而且T*恰好包含了算法 第K+1步选择的边在内。这就证明了算法到K+1步仍旧会得到一棵 最小的生成树。算法的时间复杂度, 算法会执行O(n)次,因为它每次挑一条边, 一共要挑n-1条边,而每次执行的时候要比较S跟V-S 关联的那些边里面哪条最短,这个工作量应该也是O(n)的工作量.所以总的算法的工作量 可以达到n平方。当然如果要使用一些更巧妙的数据结构, 还可以把这个时间复杂度还可以再降下来。 把这一讲的内容小结一下。Prim算法的设计 它是一个贪心的策略,它是从连接S和V-S的 所有的边里边挑那条最短的边,加到树里面去。 正确性的证明是对步数进行归纳, 给出了算法的伪码。 该算法的时间复杂度粗略地分析 它可以达到n平方,啊,是这样的一个复杂度。 这是关于Prim算法的介绍。