广度优先搜索在图论中的应用分析研究 计算机科学与技术专业VIP专享

广度优先搜索在图论中的应用摘要：本文详细地分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。关键词：广度优先搜索，最短路径，图论。Abstract：this paper gives a detailed analysis of the breadth-first search algorithm, and emphasis on the algorithm in the application of graph theory, especially in the shortest path problem in the application. Through the comparative analysis with the other shortest path search algorithm, this paper obtains these relationships between these shortest path algorithms.Keywords: breadth first search, shortest path, graph theory.目录摘要---------------------------------------------------------------------------------------------------------------0Abstract----------------------------------------------------------------------------------------------------------0一、引言---------------------------------------------------------------------------------------------------2二、广度优先搜索算法---------------------------------------------------------------------------------2(一)基本思想------------------------------------------------------------------------------------------2(二)算法结构------------------------------------------------------------------------------------------4(三)算法特性------------------------------------------------------------------------------------------5(四)广度优先搜索算法在图论中的应用---------------------------------------------------------6三、广度优先搜索算法在图论中应用的具体分析------------------------------------------------7(一)寻找连接元件------------------------------------------------------------------------------------7(二)测试是否二分图---------------------------------------------------------------------------------7(三)寻找非加权图中任两点的最短路径---------------------------------------------------------7四、最短路中常用算法的比较---------------...