最小生成树问题提出：要在n个城市间建立通信联络网，城市间的通信线路造价不同，希望找到一种方案使得建立该通信网所需花费的总代价最小。问题分析：n个城市间，最多可设置n(n-1)/2条线路；n个城市间建立通信网，至少需n-1条线路；问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）连起来，且总耗费（各边权值之和）最小。定义：生成树中边的权值（代价）之和最小的树。构造最小生成树的准则：必须只使用该网中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。实例：普里姆(Prim)算法普里姆方法的思想：1）在图中任取一个顶点K作为开始点，令U={k}