广度搜索666

假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树,简称为最小生成树问题。一棵生成树的代价就是树上各边的代价之和。 构造最小生成树可以有多种算法,下面我们介绍普里姆算法(PRIM)和克鲁斯卡尔算法(KRU