广度优先搜索在图论中的应用
摘要：本文详细地分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。
关键词：广度优先搜索，最短路径，图论。
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.
目录
摘要 ------------------------------------------------------------------------------------------------------- 0 Abstract --------------------------------------------------------------------------------------------------- 0 一、 引言 -------------------------------------------------------------------------------------------- 2 二、 广度优先搜索算法 --------------------------------------------------------------------------- 2
(一)
(二) (三)
基本思想 ----------------------------------------------------------------------------------- 2 算法结构 ----------------------------------------------------------------------------------- 4 算法特性 ----------------------------------------------------------------------------------- 5
(四) 广度优先搜索算法在图论中的应用----------------------------------------------------- 6 三、 广度优先搜索算法在图论中应用的具体分析 -------------------------------------------- 7
(一)
寻找连接元件 ------------------------------------------------------------------------------ 7
(二) 测试是否二分图 --------------------------------------------------------------------------- 7
(三) 寻找非加权图中任两点的最短路径----------------------------------------------------- 7 四、 最短路中常用算法的比较------------------------------------------------------------------- 9 五、 总结 ------------------------------------------------------------------------------------------ 10 参考文献 ------------------------------------------------------------------------- 错误！未定义书签。 附件 ----------------------------------------------------------------------------------------------------- 10
1
一、 引言
使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导和采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。
常见的搜索算法有广度优先搜索法（简称为BFS）、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、枚举法、分支定界法等。
图论是数学的一个分支,以图为研究对象。这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系。用点代表事物,用连接两点的线表示两个事物之间具有特定关系。
图论起源于18世纪,追朔到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题。从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支。
本文讨论广度优先搜索在图论中的应用。
二、 广度优先搜索算法
(一) 基本思想
采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题
2
所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。
广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n +1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。
广度优先搜索算法的搜索顺序如下图：
A B C D E F G H I J K L M 广度优先搜索顺序如下： A->B->C->D->E->F->G->H->I->J->K-L->M
广度优先搜索算法中，为了便于进行搜索，要设置一个表存储所有的结点，为了满足先生成的结点先扩展的原则，存储结点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出结点进行扩
3
展。对生成的新结点，要检查它是否已在队列中存在，还要检查它是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出结点进行扩展......。最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析。
(二) 算法结构
数据初始化；设队列首指针CLOSED：=0；队尾指针OPEN：=1； 初始结点入队； REPEAT
CLOSED：=CLOSED+1； 取下一个CLOSED所指结点； FOR R：=1 TO MAXR DO {共有MAXR种操作方法,试第R种} BEGIN
IF 子结点符合条件 THEN BEGIN
4
广度优先搜索及其应用
