边权相同的最小生成树改进算法

针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案.     

基于Prim算法的度约束最小生成树问题研究

针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.     

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

求最小生成树的矩阵算法

最小生成树问题是运筹学网络优化中一个常见的基本问题．提出了一种新的求最小生成树的矩阵算法，此算法可以不必在原图上进行操作而得到最小生成树，过程简单易懂．     

寻找最小生成树的补图算法

提出了一种关于最小生成树的生成法，该算法与传统的prim算法及kruskal算法比较，有更低的计算复杂性．     

寻找最小生成树的补图算法

提出了一种关于最小生成树的生成法,该算法与传统的prim算法及kruskal算法比较,有更低的计算复杂性.     

寻找最小生成树的度优先算法

利用Ｋｒｕｓｋａｌ和Ｐｒｉｍ算法的优点，从图的每个顶点的度数入手，采取删除某些无用边的思想方法，给出了一个寻找最小生成树的算法。算法的最坏复杂度为Ｏ（ｍ－ｎ）ｌｏｇｍ），平均复杂度为Ｏ（（ｍ－ｎ）ｌｏｇｎ），就复杂度的常数因子而言，均优于Ｋｒｕｓｋａｌ算法与ｋｉｍ算法，其中ｍ为图的边数，ｎ为图的顶点数。     

最小生成树的应用及有效算法

计算机的应用将现代数学理论引入了工程技术中。通过最小生成树在矿井通风设计和改造最优化方面的作用，阐明了最小生成树的广泛应用，并且结出了求解最小生成的简单易行的算法。     

最小生成树的算法及其应用

Kruskal算法和Prim算法是求最小生成树的常用算法.设计了这两种算法的C语言程序,并通过实例表明了算法的应用.     

受限最小生成树算法在城镇管网布局优化中的应用研究

随着天然气输配管网规模的大型化,管网系统进一步优化对提高运行的经济效益和利用率显得非常重要.采用受限最小生成树算法对城镇燃气管网布局进行优化,并将该算法与最小生成树算法(prim)进行了比较.仿真表明,该算法实用性强,对城镇天然气系统工程投资的评估预算有重要的参考价值.     

基于扩展双链式存储结构的最小生成树算法

在图的一种双链式存储结构的基础上提出了一种扩展的双链式存储结构.并用这种存储结构实现了图的最小生成树算法,与其它存储结构相比具有更好的灵活性.     

多处理器上求最小生成树的并行算法

目的给出无向图Ｇ（Ｖ,Ｅ）,｜Ｖ｜＝ｎ的最小生成树在单指令流多数据流（ＳＩＭＤ）机器、Ｉｎｃｏｍｐｌｅｔｅ－ｈｙｐｅｒｃｕｂｅ上的并行算法．方法利用有ｐ个处理器的不完全超立方网络,求加权无向连通图Ｇ（Ｖ,Ｅ）,｜Ｖ｜＝ｎ的最小生成树．结果与结论若处理器的个数为ｐ,则其时间复杂性为ｔ（ｎ）＝Ｏ（ｎ２／ｐ·（ｌｂｐ））,成本Ｃ（ｎ）＝Ｏ（ｎ２（ｌｂｐ））,它几乎是最优的．     

用遗传算法求最小生成树

以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了＂无性生殖＂的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树.     

基于遗传算法度约束的最小生成树问题的研究

探讨了如何将遗传算法应用于度约束的最小生成树问题，并给出了相应的算法．实验结果表明，这种用遗传算法解决度约束的最小生成树问题是有效的．     

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

度、直径约束最小生成树问题及其算法

提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.