资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
求无向连通图的最小生成树算法Prim 与 Kruskal 及相关优化最小生成树是图论里很重要的部分。但是由于它属于图论所以 NOIP 基本不考,对于 NOI 又太基础,所以竞赛中出现的几率比较小,即使要考也不可能考裸的生成树算法= =最小生成树就 Prim 和 Kruskal 两个算法,又没有多大的优化余地,所以学习起来还是很简单的。 一.Prim 算法1.算法思想对于图 G=(V,E),用 Prim 算法求最小生成树 T=(S,TE)的流程如下 初始化:设 S、TE 为空集,任选节点 K 加入 S。 选取一条权值最小的边(X,Y),其中 XS,且 not (YS) 即,选取一条权值最小的、连接着 S 中一点与 S 外一点的边。将 Y 加入 S 中,边(X,Y)加入 TE 中重复 直到 V=S 即所有 G 中的点都在 S 中,此时的 T 为 G 的最小生成树。由此流程可见,Prim 算法求最小生成树时任何时候的 T 都是一颗树。2.实现显然,Prim 算法的主要运行时间花在过程的选边中。看起来复杂度是 O(VE)=O(V3)不是么,效率也太低了吧为了比较快速地选边,我们用两个数组 lowcost、closest 动态地维护每一个点到 S 的最短距离。在某一状态下,lowcosti表示所有与 i 相连且另一端点在 S 中的边中的权值最小值,closesti表示在 S 中且与 i 相连的点中与 i 之间距离最小的点。显然,lowcosti=w(i,closesti)。需要注意的是两个数组记录的都是边而不是路径。若 i 没有边直接连向 S,则 lowcosti=。另外,若 i 已在 S 中,则 lowcosti=0。设出发点为 x。初始时对于任意 kV,closestk=x,lowcostk=w(k,x)【w(i,j)表示 i、j 间的距离。初始化时,若两点间没有边则w(i,j)赋为一个足够大的整数(如 maxint),并且所有点到自身的距离赋为 0,即 w(i,i)=0】每一次找出 lowcost 中不为 0 的最小值 lowcosti,然后把 i 加入S(即 lowcosti:=0),然后对于图中所有点 k,若 w(k,i)_2n2+4n】当然,邻接矩阵实际上根本用不上,把邻接表的基类型改成 record 记录端点和权值就省掉了 n2 的空间,但是实际上是我太懒了
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号