广度优先搜索在图论中的应用摘要：本文详细的分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。关键词：广度优先搜索，最短路径，图论。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.目录摘要0Abstract0一、引言2二、广度优先搜索算法2（一）基本思想2（二）算法结构3（三）算法特性4（四）广度优先搜索算法在图论中的应用5三、广度优先搜索算法在图论中应用的具体分析5（一）寻找连接元件5（二）测试是否二分图5（三）寻找非加权图中任两点的最短路径5四、最短路中常用算法的比较7五、总结7参考文献8附件8一、引言使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导和采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。常见的搜索算法有广度优先搜索法（简称为 BFS）、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、枚举法、分支定界法等。图论是数学的一个分支,以图为研究对象。这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系。用点代表事物,用连接两点的线表示两个事物之间具有特定关系。图论起源于 18 世纪,追朔到 1736 年瑞士数学家 L.Euler 出版第一本图论著作,提出和解决著名 Konigsberg 七桥问题。从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广1泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支。本文讨论广度优先搜索在图论中的应用。二、广度优先搜索算法（一）基本思想采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题所给定的...
