《求无向连通图的最小生成树算法》由会员分享，可在线阅读，更多相关《求无向连通图的最小生成树算法（6页珍藏版）》请在金锄头文库上搜索。
1、求无向连通图的最小生成树算法Prim 与 Kruskal 及相关优化最小生成树是图论里很重要的部分。但是由于它属于图论所以 NOIP 基本不考，对于 NOI 又太基础，所以竞赛中出现的几率比较小，即使要考也不可能考裸的生成树算法= =最小生成树就 Prim 和 Kruskal 两个算法，又没有多大的优化余地，所以学习起来还是很简单的。 一.Prim 算法1.算法思想对于图 G=(V,E)，用 Prim 算法求最小生成树 T=(S,TE)的流程如下 初始化：设 S、TE 为空集，任选节点 K 加入 S。 选取一条权值最小的边（X,Y），其中 XS，且 not (YS） 即，选取一条权值最小的、连
2、接着 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 相连
3、的点中与 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 的空间，但是实际上是我太懒了
