最小生成树的prim算法及minimum函数 推荐.pdfVIP

维普资讯 第 l8卷第1期 山 东 轻 工 业 学 院 学 报 V01．18No．1 2O04年3月 J0URN^JLOFsHANDoNG咖 胍 0FIII姗’ 腿 lIS『TRY Mar． 最小生成树的prim算法及minimum函数 王晓柱．翟延富。孙吉红 (山东轻工业学院计算机科学技术系，山东济南 250l0o) 摘要：本文介绍了最小生成树的 算法，minimum函数的实现过程及该函数对由pri算法所得到的 最小生成树的影响。 关键词：最小生成树；prim算法；miniratun函数 中图分类号：Tlr：319 文献标识码：A 文章编号：1004—42S0(2040)OZ一0006—04 在带权连通平面图中求最小生成树，是图论的基本问题之一，在实际工作中也有很重要的 意义。如城市间通信网的建立、公路交通网的设计等。对该问题的两个比较典型的算法是 krmkal算法和prim算法。 krmkal算法从理论上给出了求最小生成树的原则，但没有给出具体的求解方法，对于比较 简单的图形，根据krmkal算法的思想，利用观察法可求出最小生成树。 而prim算法适合于较为复杂的带权连通图。利用C语言等带有函数库的编程语言．先编 写出针对于prim算法的mininlllm函数，再调用该函数，即可利用prim算法求出最小生成树。 这样，对于较为复杂的带权连通图，就显得很简单、方便。下面就介绍一下prim算法的基本思 想和minimum函数的编制、调用方法。 1prim算法的基本思想 定理：假设N=(V，{E})是一个连通网，U是V的一个非空子集。若(u，v)是一条具有最小 权值的边，其中uEU，vEV—U，则必存在一棵包含(u，v)的最小生成树。 证明：假设所求得的最小生成树不包括(U，v)，由最小生成树的性质，加入(U，v)后必形成 一 环。设环上有另一边(u’，v’)，则U与u’，v与v’之间必有通路，删去(U’，v’)，得到一生成 树，由于(u，v)的权值小于(u’，v’)的权值，故包含(u，v)的生成树才是最小生成树，这与假设是 矛盾的。所以所求得的最小生成树必包含(u，v)。 2 prim算法的实现过程 设，IE是N上最小生成树中边的集合。算法从U={UO}(uoEV)，TE=D开始，重复执行下 收稿El期：200B一0B一26 ‘ 作者简介：王晓柱(19 一)，男，山东省招远市人，山东轻工业学院副教授、硕士，主要研究方向为多媒体技术、计算机控制技术 维普资讯 第l期 王晓柱等：最小生成树的prim算法及minilnuln函数 7 述操作：在所有uEU，vEV—U的边(u，v)∈E中找一条最小权值的边(uO，v0)归人TIE中，同时 v0并人U中．直到U=V为止。此时TIE中必有n一1条边，则T=(V，1E)为N的最小生成树。 为实现这个算法需设置一个辅助数组closed铲[唧 廿]，以记录从u到V—u中具有最小权值的 边。对每个顶点vEV—U，在辅助数组中需设置一个分量cl [v]，它包括两个域，其中 lowcost存储该边上的权。(显然，closed [v]．1owcost=Min{cost(U，v)IuEU})，vex存储该边所 关联的U中的顶点。 3 minimum函数 minilnuln函数的功能应是求U中与V—U中结点间的边中权值最小的边在V—U中的结 点。但当权值最小的边有多条时，选取规则的不同，可能会导致最后得到的最小生成树的不 同。下面通过两个例子来说明这一点。 例1求图1由prim算法所得出的最小生成树。 显然，在没有明确mininluln函数的最小边的选取规则的情况下，该题应有两个解，即在原 图中去掉边(2，4)，(2，5)，(4，6)，(4，7)，(3，8)的情况下再去掉边(1，6)或(27)所得到的最小生 成树。 例2 如图2，以H为初始点，按pri