并行计算优化：图的广度优先遍历算法研究

"这篇论文主要探讨了图的并行广度优先遍历算法，通过在Cilk++运行时系统上实现优化以及在分布式系统上应用邻接矩阵一维划分的方法，提高了传统串行广度优先搜索算法的效率。" 广度优先遍历(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法，它从根节点开始，逐层地访问所有相邻节点，然后再进入下一层节点。在图的遍历中，BFS通常用于寻找最短路径或发现连通性。在计算机科学中，尤其是在处理大规模数据结构时，提高算法效率至关重要，特别是在网络技术的迅速发展和并行计算平台的普及背景下。 这篇论文首先概述了并行广度优先搜索算法的研究背景和发展情况，强调了算法并行化的必要性。接着，作者在Cilk++并行编程环境中，利用"bag"数据结构替代了传统的共享队列，这是一种基于层同步思想的细粒度并行算法。这种方法减少了竞争条件，简化了并行代码的编写，从而提升了算法的执行效率。 随后，论文进一步探讨了在分布式系统上的实现，提出了基于邻接矩阵一维划分的并行广度优先搜索算法。在分布式系统中，这种方法能有效地分散计算任务，利用多节点的并行计算能力，提高整体的计算速度。 论文的最后部分是对现有并行BFS算法的分析和研究，作者在此基础上提出了可能的改进策略和未来的研究方向。通过这种方式，论文不仅展示了并行计算在优化图遍历算法上的潜力，也为后续研究者提供了有价值的参考和启示。 这篇由霍红卫教授指导，杨爱民同学完成的学位论文深入研究了如何通过并行化技术优化图的广度优先遍历，其研究成果对于理解和改善大规模图处理的效率具有重要意义。论文遵循了严格的学术规范，确保了研究的原创性和真实性，并同意西安电子科技大学保留和使用学位论文的相关权益。