精选优质文档-倾情为你奉上最小生成树的多核并行算法马成刚（）摘要：最小生成树是图论中的经典问题，在现实生活中也有很多应用。本文讨论一种最小生成树的多核并行算法。关键字：最小生成树；索林算法；并行专心-专注-专业一、介绍最小生成树问题是图论中的一个经典问题，也是众多广泛应用的问题之一。关于最小生成树问题已有一些经典的算法，如：Prim算法、Kruskal算法，都具有近线性的算法复杂度。对于稀疏图来说，使用Kruskal算法更好，否则两种算法复杂性没有什么区别【1】。Prim算法每次选择一个顶点，Kruskal算法每次选择一条边，下一个顶点或边是否选择与以前选的顶点或边有关，这样都不适合于并行计算，即当今的多核计算机不能太大提高计算效率。本文介绍一种基于Sollin算法的求解最小生成树的多核并行算法，能够提高求最小生成树的并行效率。二、算法先给出Sollin算法从连通带权简单图G=（V，E）这样产生最小生成树：相继地添加成组的边。假定对V里的顶点进行了排序，这样就产生了一个顺序，其中若u0先于u1，或者若u0=u1并且v0先于v
