假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄位置大致如图7-6-1，其中v 0 ～v8 是村庄，之间连线的数字表示村与村间的可通达的直线距离，比如v 0 至v 1 就是10公里（个别如v0 与v6 ，v6与v 8 ，v 5 与v 7 未测算距离是因为有高山或湖泊，不予考虑）。你们领导要求你必须用最小的成本完成这次任务。你说怎么办？
    image.png
    显然这是一个带权值的图，即网结构。所谓的最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使得权值的和最小。在这个例子里，每多一公里就多一份成本，所以只要让线路连线的公里数最少，就是最少成本了。

    如果你加班加点，没日没夜设计出的结果是如图7-6-2的方案一（粗线为要架设线路），我想你离被炒鱿鱼应该是不远了（同学微笑）。因为这个方案比后两个方案多出60%的成本会让老板气晕过去的。
    image.png
    方案三设计得非常巧妙，但也只以极其微弱的优势对方案二胜出，应该说很是侥幸。我们有没有办法可以精确计算出这种网图的最佳方案呢？答案当然是Yes。

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

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