2023年8月1日发(作者：)

计算机光盘软件与应用　２０１０年第３期　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　软件设计开发　基于Ｐｒｉｍ算法和Ｋｒｕｓｋａｌ算法的最小生成树优化研究　李仙玉　（肇庆科技职业技术学院信息工程系，广东肇庆摘５２６０２０）　要：文章从目前最常见的两种在图最小生成树算法，即Ｐｒｉｍ和Ｋｒｕｓｋａｌ算法，展开了阐述和分析，运用了大量的数据　和实例对这两种计算方法进行了分析和研究。通过试验并对Ｐｒｉｍ算法进行改进，从图中每个顶点的度数入手，采取删除某些无　用边的思想方法，给出了一个寻找最小生成树的算法，使其能动态调整自身的性能，既适合于稠密图，又适合于稀疏图。　关犍词：Ｐｒｉｍ算法；最小生成树；Ｋｒｕｓｋａｌ算法　中目分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１００７－９５９９（２０１０）０３—００９５—０２　Ｒｅｓｅａｒｃｈ　Ｍｉｎｉｍｕｍ　Ｓｐａｎｎｉｎｇ　Ｔｒｅｅ　Ｂａｓｅｄ　ｏｎ　Ｐｒｉｍ　Ａｌｇｏｒｉｔｈｍ　ｔ．ｉ　Ｘｉａｎｙｕ　（Ｚｈａｏｑｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｅｎｇｉｎｅｅｒｉｎｇ，ＺｈａｏＱｉｎｇ　５２６０２０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｇｒａｐｈ，Ｐｒｉｍ　ａｎｄ　Ｋａ＇ｕｓｋａｌ　ａｌｇｏｒｉｔｈｍ　ａｌｅ　ｒｅｓｐｅｃｔｉｖｅｌｙ　ａｐｐ￣ｅｄ　ｔｏ　ｄｅｎｓｅ　ｇｒａｐｈ　ｎｄ　ａｓｐａｒｓｅ　ｒａｐｈ．Ｂｕｔｇ　ｂｏｔｈ　ｃａｎｌｌｏｔ　ｄｙｎａｍｉｃａｌｌｙ　ｒｅｇｕｌａｔｅ　ｈｅｉｔｒ　ｏｗｎ　ｃａｐａｂｉ￣ｔｙ　ｂａｓｅｄ　ｏｎ　ｐｅａｋ　ｎｕｍｂｅｒ，ｅｄｇｅ　ｎｕｍｂｅｒ　ａｎｄ　ｅｄｇｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｐｒｉｍ　ｓｔａｒｔｓ　ｆｒｏｍ　ｔｈｅ　ｄｅｇｒｅｅ　ｏｆ　ｔｈｅ　ｖｅｇｅｘ　ａｎｄ　ｔｈｅｎ　ｄｅｌｅｔｅ　ｓｏｍｅ　ｕｓｅｌｅｓｓ　ｅｄｇｅｓ　ｆｒｏｍ　ｔｈｅ　ｇｒａｐｈ．Ｔｈｅｒｅｆｏｒｅ，　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｎ　ｔｈｅ　Ｐｒｉｍ　ａｌｇｏｒｉｔｈｍ，ｅｎａｂｌｉｎｇ　ｉｔ　ｄｙｎａｍｉｃａｌｌｙ　ｒｅｇｕｌａｔｅｓ　ｉｔｓ　ｃａｐａｂｉｌｉｔｙ，Ｃａｎ　ｂｅ　ａｐｐｌｉｅｄ　ｔｏ　ｂｏｔｈ　ｄｅｎｓｅ　ｒａｐｈ　ｇｎｄ　ａｓｐａｒｓｅ　ｇｒａｐｈ．　Ｋｅｙｗｏｒｄｓ：Ｐｒｉｍ　ａｌｇｏｒｉｔｈｍ；Ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ；ＩＣｒｕｓｋａｌ　ａｌｇｏｒｉｔｈｍ　最小生成树是数据结构中图的一种重要应用，它的要求是从一　个带权无向完全图中选择ｎ一１条边并使这个图仍然连通（也即得　到了一棵生成树），同时还要考虑使树的权最小。为了得到最小生　成树，人们设计了很多算法，最著名的有ｐｒｉｍ算法和ｋｒｕｓｋａｌ算法。　一然后随便从右边的集合中拿出　个数到左边的集合来，并搜出　它与　他的点所订连线酚值。　从图中可以看到１到３的距离是最短的，所以８一定为最小生　成树中的一段，所以我们将３放入左边的集合，然后把８这个数加　到ａｉｉｓ里面去。并用３到右边的集合中的点的距离去刷新１到右边　、ＰＲＩＭ算法：　与Ｄｉｊｓｔｒａ算法类似，具体操作是：从图中任意一个顶点开始，　集合的点的距离。　首先把这个顶点包括在ＭＳＴ里，然后在那些其一个端点已在ＭＳＴ里，　另一个端点还不是ＭＳＴ里的边，找权最小的一条边，并把这条边和　其不在ＭＳＴ里的那个端点包括进ＭＳＴ里。如此进行下去，每次往ＭＳＴ　里加一个顶点和一条权最小的边，直到把所有的顶点都包括进ＭＳＴ　里。以上代码中的ｍｉｎＶｅｒｔｅｘ函数，可用最小堆等方式实现。任取　一个顶点加入生成树，然后对那些一个端点在生成树中，而另～个　端点不在生成树中的边进行排序，取权值最小的边，将它和另一个　端点加进生成树中。重复步骤直到所有顶点都加进了生成树。　首先我们对于一个样例来分析：　４　Ｏ　１６　８　９　ｌ６　０　３　６　８　３　０　ｉ０　所以我们第二次就墩３　２的趴高为３，加到ａｎｓ里面，然后　２拿过来，蹲刷新距离　９　６　１Ｏ　Ｏ　然后ａｆｌｓ加６，再把４从右边的集合给拿过来，这是右边集合　空了，ＰＲＩＭ结束。ａｎｓ＝８＋３＋６＝１７最小生成数为：　我们有两个集合来操作：　（下转第９４页）　９５一　一计算机光盘软件与应用　多媒体技术及应用　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　参考文献：　２０１０年第３期　４．利用数字收发箱和邮件与教师进行交流的学习。　数字收发箱是网络在线学习系统平台的一个功能，学生可以向　教师发送文件。有些因为各种原因课上没有完成实践任务的学生，　可以在课下完成该任务，然后利用数字收发箱或邮件发给教师。　四、结束语　［１１纪红，郭公民．多媒体辅助教学现状的分析卟北京农学院学　报，２００７，Ｓｌ　［２１４秀峰，李晓飞．虚拟学习社区——教师专业发展的新平台ｉｆ］．电化　教育研究，２００９，４　作者简介　混合学习模式作为当前一种新型教学模式，融合了传统教学模　式以及计算机网络教学的多重优势，我们应当充分发挥其优势，为　当前高职计算机教学的发展提供强有力的工具。　邹嫒（１９７３．１２一），女，湖南娄底人，湖南娄底职业技术学院，大　学学历，计算机系讲师，主要从事计算机教学研究。　（上接第９５页）　选取的边若产生环路则不可能形成一棵生成树。Ｋｒｕｓｋａｌ算法分ｅ步，　其中ｅ是网络中边的数目。按耗费递增的顺序来考虑这ｅ条边，每次考　虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环　如上图所示，假设Ｅ是图中边的集合，Ｖ是图中的顶点的集合，　ＴＥ为最小生成树中的边的集合，则ｐｒｉｍ算法可以通过以下步骤实现　最小生成树：　路，则将其抛弃，否则，将它选入。　初始时没有任何边被选择。边（１，６）是最先选入的边，它被　（一）首先初始化ＴＥ＝（０｝，ｕ＝｛ｕ　０）。此步骤设立一个初始行态　即只有结点ｕ　０的结点集ｕ和一个空的边集ＴＥ作为最小生成　加入到欲构建的生成树中，得到图１３—１２ｃ。下一步选择边（３，４）　并将其加入树中（如图１３—１　２ｄ所示）。然后考虑边（２，７，将它　树的，在后面的算法执行过程中，这种行态会不断的发生变化，直到　生成最小生成树，循环终止。　（二）在所有ｕ∈ｕ，ｖ∈Ｖ—ｕ的边（ｕ，ｖ）∈Ｅ中，搜索一条权　值最小的边（ｕ　０，ｖ　０），同时将（ｕ　０，ｖ　０）边加进到集合ＴＥ中，　同时寻找到此边的非ｕ的中顶点，并且将此顶点中加入到ｕ中。此　加入树中并不会产生环路，于是便得到图１３　１２ｅ。下一步考虑边（２，　３）并将其加入树中（如图１３－１２ｆ所示）。在其余还未考虑的边中，　（７，４）具有最小耗费，因此先考虑它，将它加入正在创建的树中　会产生环路，所以将其丢弃。此后将边（５，４）加入树中，得到的　树如图１３—１２ｇ所示。下一步考虑边（７，５），由于会产生环路，　将其丢弃。最后考虑边（６，５）并将其加入树中，产生了一棵生成　步骤的功能是在边集Ｅ中找一条边，要求这条边满足以下条件：首　先边的两个顶点要分别在顶点集合ｕ和Ｖ—ｕ中，其次边的权要最　小。找到这条边以后，把这条边放到边集ＴＥ中，并把这条边上不在ｕ　树，其耗费为９９。　中的那个顶点加入到ｕ中。这一步骤在算法中应执行多次，每执行　一对于图Ｇ＝（Ｖ，Ｅ），开始时，将顶点集分为ＩＶ１个等价类，每　个等价类包括一个顶点；然后，以权的大小为顺序处理各条边，如　次，集合ＴＦ和ｕ都将发生变化，分别增加一条边和一个顶点，因　此，．ｒＥ和ｕ是两个动态的集合，这一点在理解算法时要密切注意。　（三）如果Ｖ等于ｕ，算法结束，否则继续重复步骤２。我们可　以把本此判断当做是循环终止的条件。还可以通过算出当ｕ等于ｖ　时，步骤２一共执行了ｎ一１次（其中将图中顶点的数目设为ｎ），ＴＥ　中同样也增加了ｎ一１条边，需要求出的最小生成树的边即这ｎ一１　条边。　果某条边连接两个不同等价类的顶点，则这条边被添加到ＭＳＴ，两　个等价类被合并为一个；反复执行此过程，直到只剩下一个等价类。　采用Ｋｒｕｓｋａｌ算法计算最小支撑树的例子：　连通网用邻接矩阵ｎｅｔ表示，若两个顶点之间不存在边，其权值　为计算机内允许最大值，否则为对应边上的权值。　此算法的精妙之处在于对求权值最小的边这一问题的分解（也　正是由于这种分解，而导致了算法理解上的困难）。按照常规的思　路，这一问题应该这样处理：分别从集合ｕ和集合ｖ—ｕ中取一顶点，　并且从邻接矩阵中找到这两个顶点行形成的边的权值。同时设Ｕ中　有ｎ个顶点，Ｖ—ｕ中有ｍ个顶点。即需要找到ｍ★ｎ个权值，在这　从分析Ｐｒｉｍ算法中我们得出，如果网中有ｎ个顶点，则将第一个　对数组初始化的频度设为ｎ，第二个将其余顶点并入到集合的ｕ循环语　句的频度为ｎ—ｌ，其中还包括两个内循环：一个是重新修正最小权值　些个权值中，再查找权值最小的边。每执行一次循环，这一查找过程　都应重复一次，计算任务比较繁重。而本算法则利用了变量ｔｒｅｅ　中第ｎ一１元素到第ｋ＋ｌ号元素来存放到上一循环为止的相关比较　结果，如果以第ｋ＋１号元素为例说明，其存放的是集合ｕ中某一顶　点到顶点ｔｒｅｅ．ｅｎ的边，即这条边是到该点的所有边中权值最小（最　优）的边，所以，求权最小的边这一问题，通过比较第ｎ—ｌ号到第ｋ　＋１号元素的权值的大小就可以解决，每次循环这需要比较ｎ—ｋ一２　次即可，大大减小了运算量。　二、Ｋｒｕｓｋａｌ算法　Ｋｒｕｓｋａｌ算法也称边割法，是Ｐｒｉｍ于１９５７年提出的。Ｋｒｕｓｋａｌ算法　的边，一个是选取最小权值的边频度为ｎ，其频度为ｎ　１。可以看出，　Ｐｒｉｍ算法的时间复杂度为Ｏ（ｎ　），与网中的边数无关，因此，该算　法适合求边稠密网的最小生成树。从分析Ｋｒｕｓｋａｌ算法中我们可以发　现Ｋｒｕｓｋａｌ算法与Ｐｒｉｍ算法恰恰相反，它的时间复杂度为０（ｍｌｏｇｍ），　ｍ为网中边的数目。因此，它相对于Ｐｒｉｍ算法而言，适合于求边稀疏　的网的最小生成树。　参考文献：　［１］高一凡《数据结构》算法实现及解析．西安：西安电子科技大学出　版社．２００２　每次选择ｎ—ｌ条边，所使用的贪婪准则是：从剩下的边中选择一条不　会产生环路的具有最小耗费的边加入己选择的边的集合中。注意到所　【２】廖荣贵．数据结构与算法北京：清华大学出版社，２００４　・－——９４　。——　

2023年8月1日发(作者：)

计算机光盘软件与应用　２０１０年第３期　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　软件设计开发　基于Ｐｒｉｍ算法和Ｋｒｕｓｋａｌ算法的最小生成树优化研究　李仙玉　（肇庆科技职业技术学院信息工程系，广东肇庆摘５２６０２０）　要：文章从目前最常见的两种在图最小生成树算法，即Ｐｒｉｍ和Ｋｒｕｓｋａｌ算法，展开了阐述和分析，运用了大量的数据　和实例对这两种计算方法进行了分析和研究。通过试验并对Ｐｒｉｍ算法进行改进，从图中每个顶点的度数入手，采取删除某些无　用边的思想方法，给出了一个寻找最小生成树的算法，使其能动态调整自身的性能，既适合于稠密图，又适合于稀疏图。　关犍词：Ｐｒｉｍ算法；最小生成树；Ｋｒｕｓｋａｌ算法　中目分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１００７－９５９９（２０１０）０３—００９５—０２　Ｒｅｓｅａｒｃｈ　Ｍｉｎｉｍｕｍ　Ｓｐａｎｎｉｎｇ　Ｔｒｅｅ　Ｂａｓｅｄ　ｏｎ　Ｐｒｉｍ　Ａｌｇｏｒｉｔｈｍ　ｔ．ｉ　Ｘｉａｎｙｕ　（Ｚｈａｏｑｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｅｎｇｉｎｅｅｒｉｎｇ，ＺｈａｏＱｉｎｇ　５２６０２０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｇｒａｐｈ，Ｐｒｉｍ　ａｎｄ　Ｋａ＇ｕｓｋａｌ　ａｌｇｏｒｉｔｈｍ　ａｌｅ　ｒｅｓｐｅｃｔｉｖｅｌｙ　ａｐｐ￣ｅｄ　ｔｏ　ｄｅｎｓｅ　ｇｒａｐｈ　ｎｄ　ａｓｐａｒｓｅ　ｒａｐｈ．Ｂｕｔｇ　ｂｏｔｈ　ｃａｎｌｌｏｔ　ｄｙｎａｍｉｃａｌｌｙ　ｒｅｇｕｌａｔｅ　ｈｅｉｔｒ　ｏｗｎ　ｃａｐａｂｉ￣ｔｙ　ｂａｓｅｄ　ｏｎ　ｐｅａｋ　ｎｕｍｂｅｒ，ｅｄｇｅ　ｎｕｍｂｅｒ　ａｎｄ　ｅｄｇｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ．Ｐｒｉｍ　ｓｔａｒｔｓ　ｆｒｏｍ　ｔｈｅ　ｄｅｇｒｅｅ　ｏｆ　ｔｈｅ　ｖｅｇｅｘ　ａｎｄ　ｔｈｅｎ　ｄｅｌｅｔｅ　ｓｏｍｅ　ｕｓｅｌｅｓｓ　ｅｄｇｅｓ　ｆｒｏｍ　ｔｈｅ　ｇｒａｐｈ．Ｔｈｅｒｅｆｏｒｅ，　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｎ　ｔｈｅ　Ｐｒｉｍ　ａｌｇｏｒｉｔｈｍ，ｅｎａｂｌｉｎｇ　ｉｔ　ｄｙｎａｍｉｃａｌｌｙ　ｒｅｇｕｌａｔｅｓ　ｉｔｓ　ｃａｐａｂｉｌｉｔｙ，Ｃａｎ　ｂｅ　ａｐｐｌｉｅｄ　ｔｏ　ｂｏｔｈ　ｄｅｎｓｅ　ｒａｐｈ　ｇｎｄ　ａｓｐａｒｓｅ　ｇｒａｐｈ．　Ｋｅｙｗｏｒｄｓ：Ｐｒｉｍ　ａｌｇｏｒｉｔｈｍ；Ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅ；ＩＣｒｕｓｋａｌ　ａｌｇｏｒｉｔｈｍ　最小生成树是数据结构中图的一种重要应用，它的要求是从一　个带权无向完全图中选择ｎ一１条边并使这个图仍然连通（也即得　到了一棵生成树），同时还要考虑使树的权最小。为了得到最小生　成树，人们设计了很多算法，最著名的有ｐｒｉｍ算法和ｋｒｕｓｋａｌ算法。　一然后随便从右边的集合中拿出　个数到左边的集合来，并搜出　它与　他的点所订连线酚值。　从图中可以看到１到３的距离是最短的，所以８一定为最小生　成树中的一段，所以我们将３放入左边的集合，然后把８这个数加　到ａｉｉｓ里面去。并用３到右边的集合中的点的距离去刷新１到右边　、ＰＲＩＭ算法：　与Ｄｉｊｓｔｒａ算法类似，具体操作是：从图中任意一个顶点开始，　集合的点的距离。　首先把这个顶点包括在ＭＳＴ里，然后在那些其一个端点已在ＭＳＴ里，　另一个端点还不是ＭＳＴ里的边，找权最小的一条边，并把这条边和　其不在ＭＳＴ里的那个端点包括进ＭＳＴ里。如此进行下去，每次往ＭＳＴ　里加一个顶点和一条权最小的边，直到把所有的顶点都包括进ＭＳＴ　里。以上代码中的ｍｉｎＶｅｒｔｅｘ函数，可用最小堆等方式实现。任取　一个顶点加入生成树，然后对那些一个端点在生成树中，而另～个　端点不在生成树中的边进行排序，取权值最小的边，将它和另一个　端点加进生成树中。重复步骤直到所有顶点都加进了生成树。　首先我们对于一个样例来分析：　４　Ｏ　１６　８　９　ｌ６　０　３　６　８　３　０　ｉ０　所以我们第二次就墩３　２的趴高为３，加到ａｎｓ里面，然后　２拿过来，蹲刷新距离　９　６　１Ｏ　Ｏ　然后ａｆｌｓ加６，再把４从右边的集合给拿过来，这是右边集合　空了，ＰＲＩＭ结束。ａｎｓ＝８＋３＋６＝１７最小生成数为：　我们有两个集合来操作：　（下转第９４页）　９５一　一计算机光盘软件与应用　多媒体技术及应用　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　参考文献：　２０１０年第３期　４．利用数字收发箱和邮件与教师进行交流的学习。　数字收发箱是网络在线学习系统平台的一个功能，学生可以向　教师发送文件。有些因为各种原因课上没有完成实践任务的学生，　可以在课下完成该任务，然后利用数字收发箱或邮件发给教师。　四、结束语　［１１纪红，郭公民．多媒体辅助教学现状的分析卟北京农学院学　报，２００７，Ｓｌ　［２１４秀峰，李晓飞．虚拟学习社区——教师专业发展的新平台ｉｆ］．电化　教育研究，２００９，４　作者简介　混合学习模式作为当前一种新型教学模式，融合了传统教学模　式以及计算机网络教学的多重优势，我们应当充分发挥其优势，为　当前高职计算机教学的发展提供强有力的工具。　邹嫒（１９７３．１２一），女，湖南娄底人，湖南娄底职业技术学院，大　学学历，计算机系讲师，主要从事计算机教学研究。　（上接第９５页）　选取的边若产生环路则不可能形成一棵生成树。Ｋｒｕｓｋａｌ算法分ｅ步，　其中ｅ是网络中边的数目。按耗费递增的顺序来考虑这ｅ条边，每次考　虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环　如上图所示，假设Ｅ是图中边的集合，Ｖ是图中的顶点的集合，　ＴＥ为最小生成树中的边的集合，则ｐｒｉｍ算法可以通过以下步骤实现　最小生成树：　路，则将其抛弃，否则，将它选入。　初始时没有任何边被选择。边（１，６）是最先选入的边，它被　（一）首先初始化ＴＥ＝（０｝，ｕ＝｛ｕ　０）。此步骤设立一个初始行态　即只有结点ｕ　０的结点集ｕ和一个空的边集ＴＥ作为最小生成　加入到欲构建的生成树中，得到图１３—１２ｃ。下一步选择边（３，４）　并将其加入树中（如图１３—１　２ｄ所示）。然后考虑边（２，７，将它　树的，在后面的算法执行过程中，这种行态会不断的发生变化，直到　生成最小生成树，循环终止。　（二）在所有ｕ∈ｕ，ｖ∈Ｖ—ｕ的边（ｕ，ｖ）∈Ｅ中，搜索一条权　值最小的边（ｕ　０，ｖ　０），同时将（ｕ　０，ｖ　０）边加进到集合ＴＥ中，　同时寻找到此边的非ｕ的中顶点，并且将此顶点中加入到ｕ中。此　加入树中并不会产生环路，于是便得到图１３　１２ｅ。下一步考虑边（２，　３）并将其加入树中（如图１３－１２ｆ所示）。在其余还未考虑的边中，　（７，４）具有最小耗费，因此先考虑它，将它加入正在创建的树中　会产生环路，所以将其丢弃。此后将边（５，４）加入树中，得到的　树如图１３—１２ｇ所示。下一步考虑边（７，５），由于会产生环路，　将其丢弃。最后考虑边（６，５）并将其加入树中，产生了一棵生成　步骤的功能是在边集Ｅ中找一条边，要求这条边满足以下条件：首　先边的两个顶点要分别在顶点集合ｕ和Ｖ—ｕ中，其次边的权要最　小。找到这条边以后，把这条边放到边集ＴＥ中，并把这条边上不在ｕ　树，其耗费为９９。　中的那个顶点加入到ｕ中。这一步骤在算法中应执行多次，每执行　一对于图Ｇ＝（Ｖ，Ｅ），开始时，将顶点集分为ＩＶ１个等价类，每　个等价类包括一个顶点；然后，以权的大小为顺序处理各条边，如　次，集合ＴＦ和ｕ都将发生变化，分别增加一条边和一个顶点，因　此，．ｒＥ和ｕ是两个动态的集合，这一点在理解算法时要密切注意。　（三）如果Ｖ等于ｕ，算法结束，否则继续重复步骤２。我们可　以把本此判断当做是循环终止的条件。还可以通过算出当ｕ等于ｖ　时，步骤２一共执行了ｎ一１次（其中将图中顶点的数目设为ｎ），ＴＥ　中同样也增加了ｎ一１条边，需要求出的最小生成树的边即这ｎ一１　条边。　果某条边连接两个不同等价类的顶点，则这条边被添加到ＭＳＴ，两　个等价类被合并为一个；反复执行此过程，直到只剩下一个等价类。　采用Ｋｒｕｓｋａｌ算法计算最小支撑树的例子：　连通网用邻接矩阵ｎｅｔ表示，若两个顶点之间不存在边，其权值　为计算机内允许最大值，否则为对应边上的权值。　此算法的精妙之处在于对求权值最小的边这一问题的分解（也　正是由于这种分解，而导致了算法理解上的困难）。按照常规的思　路，这一问题应该这样处理：分别从集合ｕ和集合ｖ—ｕ中取一顶点，　并且从邻接矩阵中找到这两个顶点行形成的边的权值。同时设Ｕ中　有ｎ个顶点，Ｖ—ｕ中有ｍ个顶点。即需要找到ｍ★ｎ个权值，在这　从分析Ｐｒｉｍ算法中我们得出，如果网中有ｎ个顶点，则将第一个　对数组初始化的频度设为ｎ，第二个将其余顶点并入到集合的ｕ循环语　句的频度为ｎ—ｌ，其中还包括两个内循环：一个是重新修正最小权值　些个权值中，再查找权值最小的边。每执行一次循环，这一查找过程　都应重复一次，计算任务比较繁重。而本算法则利用了变量ｔｒｅｅ　中第ｎ一１元素到第ｋ＋ｌ号元素来存放到上一循环为止的相关比较　结果，如果以第ｋ＋１号元素为例说明，其存放的是集合ｕ中某一顶　点到顶点ｔｒｅｅ．ｅｎ的边，即这条边是到该点的所有边中权值最小（最　优）的边，所以，求权最小的边这一问题，通过比较第ｎ—ｌ号到第ｋ　＋１号元素的权值的大小就可以解决，每次循环这需要比较ｎ—ｋ一２　次即可，大大减小了运算量。　二、Ｋｒｕｓｋａｌ算法　Ｋｒｕｓｋａｌ算法也称边割法，是Ｐｒｉｍ于１９５７年提出的。Ｋｒｕｓｋａｌ算法　的边，一个是选取最小权值的边频度为ｎ，其频度为ｎ　１。可以看出，　Ｐｒｉｍ算法的时间复杂度为Ｏ（ｎ　），与网中的边数无关，因此，该算　法适合求边稠密网的最小生成树。从分析Ｋｒｕｓｋａｌ算法中我们可以发　现Ｋｒｕｓｋａｌ算法与Ｐｒｉｍ算法恰恰相反，它的时间复杂度为０（ｍｌｏｇｍ），　ｍ为网中边的数目。因此，它相对于Ｐｒｉｍ算法而言，适合于求边稀疏　的网的最小生成树。　参考文献：　［１］高一凡《数据结构》算法实现及解析．西安：西安电子科技大学出　版社．２００２　每次选择ｎ—ｌ条边，所使用的贪婪准则是：从剩下的边中选择一条不　会产生环路的具有最小耗费的边加入己选择的边的集合中。注意到所　【２】廖荣贵．数据结构与算法北京：清华大学出版社，２００４　・－——９４　。——