Question

假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄位置大致如图7-6-1，其中v₀～v₈是村庄，之间连线的数字表示村与村间的可通达的直线距离，比如v₀至v₁就是10公里（个别如v₀与v₆，v₆与v₈，v₅与v₇未测算距离是因为有高山或湖泊，不予考虑）。你们领导要求你必须用最小的成本完成这次任务。你说怎么办？

图7-6-1

显然这是一个带权值的图，即网结构。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。在这个例子里，每多一公里就多一份成本，所以只要让线路连线的公里数最少，就是最少成本了。

如果你加班加点，没日没夜设计出的结果是如图7-6-2的方案一（粗线为要架设线路），我想你离被炒鱿鱼应该是不远了（同学微笑）。因为这个方案比后两个方案多出60%的成本会让老板气晕过去的。

图7-6-2

方案三设计得非常巧妙，但也只以极其微弱的优势对方案二胜出，应该说很是侥幸。我们有没有办法可以精确计算出这种网图的最佳方案呢？答案当然是Yes。

我们在讲图的定义和术语时，曾经提到过，一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。显然图7-6-2的三个方案都是图7-6-1的网图的生成树。那么我们把构造连通网的最小代价生成树称为最小生成树（Minimum Cost SpanningTree）。

找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。我们就分别来介绍一下。