PAGEPAGE9广度优先搜索在图论中的应用摘要：本文详细的分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。关键词：广度优先搜索，最短路径，图论。Abstract：thispapergivesadetailedanalysisofthebreadth-firstsearchalgorithm,andemphasisonthealgorithmintheapplicationofgraphtheory,especiallyintheshortestpathproblemintheapplication.Throughthecomparativeanalysiswiththeothershortestpathsearchalgorithm,thispaperobtainstheserelationshipsbetweentheseshortestpathalgorithms.Keywords:breadthfirstsearch,shortestpath,graphtheory.目录TOC\o"1-2"\h\z\uHYPERLINK\l"_Toc261164600"摘要PAGEREF_Toc261164600\h0HYPERLINK\l"_Toc261164601"AbstractPAGEREF_Toc261164601\h0HYPERLINK\l"_Toc261164602"一、引言PAGEREF_Toc261164602\h2HYPERLINK\l"_Toc261164603"二、广度优先搜索算法PAGEREF_Toc261164603\h2HYPERLINK\l"_Toc261164604"（一）基本思想PAGEREF_Toc261164604\h2HYPERLINK\l"_Toc261164605"（二）算法结构PAGEREF_Toc261164605\h3HYPERLINK\l"_Toc261164606"（三）算法特性PAGEREF_Toc261164606\h4HYPERLINK\l"_Toc261164607"（四）广度优先搜索算法在图论中的应用PAGEREF_Toc261164607\h5HYPERLINK\l"_Toc261164608"三、广度优先搜索算法在图论中应用的具体分析PAGEREF_Toc261164608\h5HYPERLINK\l"_Toc261164609"（一）寻找连接元件PAGEREF_Toc261164609\h5HYPERLINK\l"_Toc261164610"（二）测试是否二分图PAGEREF_Toc261164610\h5HYPERLINK\l"_Toc261164611"（三）寻找非加权图中任两点的最短路径PAGEREF_Toc261164611\h5HYPERLINK\l"_Toc261164612"四、最短路中常用算法的比较PAGEREF_Toc261164612\h7HYPERLINK\l"_Toc261164613"五、总结PAGEREF_Toc261164613\h7HYPERLINK\l"_Toc261164614"参考文献PAGEREF_Toc261164614\h8HYPERLINK\l"_Toc261164615"附件PAGEREF_Toc261164615\h8一、引言使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导和采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。常见的搜索算法有广度优先搜索法（简称为BFS）、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、枚举法、分支定界法等。图论是数学的一个分支,以图为研究对象。这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系。用点代表事物,用连接两点的线表示两个事物之间具有特定关系。图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题。从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学