挑战程序设计竞赛：世界很好程序设计高手的经验总结（第2版）

本书适合程序设计人员、程序设计竞赛爱好者以及高校计算机专业师生阅读。 秋叶拓哉、岩田阳一、北川宜稔所著的《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总，分为准备篇、初级篇、中级篇与不错篇4章。作者结合自己丰富的参赛经验，对严格筛选的110多道各类试题进行了由浅入深、由易及难的细致讲解，并介绍了许多实用技巧。每章后附有习题，供读者练习，巩固所学。
《挑战程序设计竞赛(第2版)》适合程序设计人员、程序设计竞赛爱好者以及高校计算机专业师生阅读。     2.5.5 很小生成树
     给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和很小的生成树叫做很小生成树（MST，Minimum Spanning Tree）。
     例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用很小的生成树就是很小生成树问题。
     常见的求解很小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。
     1.很小生成树问题1（PrIm算法）
     首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。
     首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的很小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是很小生成树。
     ……

#现在前往