最小生成树   通俗的讲,最小生成树就是用一条路径将图中的所有顶点链接起来,并且保证该路径上的权值之和是最小的.以保证该路径的唯一.重点就在于权值的最小. 算法 普里姆算法: 该算法利用两个集合,一个是保存了,已经找到的符合条件(权值最小)的弧的顶点集合U,一个是保存了除U集合剩下的顶点的集合S. 若图G = {顶点V,  弧E}, 那么S = V - U 算法步骤: 1.初始化.选择图中的任意一个顶点u_0放到集合U中,表示选中一个顶点.U = {u_0} 2.计算S = V - U; 分别从…

2013年12月7日 0条评论 2点热度 阅读全文