论文部分内容阅读
最小生成树算法在计算机网络、信息安全等领域中有着广泛的应用,目前比较普遍的求解算法有Prim算法和Kruskal算法,但这两种算法由于本身的数据结构特性和迭代过程的相关性限制而难以并行化,因而无法有效地利用通用GPU并行架构进行并行化加速。Sollin算法虽然是最古老的最小生成树算法之一,但是在算法中经过初始化的森林迭代过程,每次迭代可以同时扩展合并多棵最小生成树,经过数次扩展和合并,最终由初始森林合并为一棵树,一旦成功扩展,这棵树一定是最小生成树。在扩展合并的过程中,每次迭代中每棵树的扩展和合并过