广度优先搜索及其应用3021.pdf

广度优先搜索在图论中的应用 摘要：本文详细地分析了广度优先搜索算法，重点研究了该算法在图论中的应用，尤其是在最短路径问题中的应用。通过与其它最短路搜索算法的比较分析，本文得到了这些最短路算法之间的关系。关键词：广度优先搜索，最短路径，图论。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.1 目录 摘要-0 Abstract-0 一、引言-2 二、广度优先搜索算法-2(一)基本思想-2(二)算法结构-4(三)算法特性-5(四)广度优先搜索算法在图论中的应用-6 三、广度优先搜索算法在图论中应用的具体分析-7(一)寻找连接元件-7(二)测试是否二分图-7(三)寻找非加权图中任两点的最短路径-7 四、最短路中常用算法的比较-9 五、总结-10 参考文献-错误!未定义书签。附件-10 2 一、引言 使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导和采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。常见的搜索算法有广度优先搜索法（简称为 BFS）、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、枚举法、分支定界法等。图论是数学的一个分支,以图为研究对象。这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系。用点代表事物,用连接两点的线表示两个事物之间具有特定关系。图论起源于 18 世纪,追朔到 1736 年瑞士数学家 L.Euler 出版第一本图论著作,提出和解决著名 Konigsberg 七桥问题。从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支。本文讨论广度优先搜索在图论中的应用。二、广度优先搜索算法(一)基本思想 采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。根据问题 3 所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，.对长度为 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 4 展。对生成的新结点，要检查它是否已在队列中存在，还要检查它是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出结点进行扩展.。最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析。(二)算法结构 数据初始化；设队列首指针 CLOSED：=0；队尾指针 OPEN：=1；初始结点入队；REPEAT CLOSED：=CLOSED+1；取下一个 CLOSED 所指结点；FOR R：=1 TO MAXR DO 共有 MAXR 种操作方法,试第 R 种 BEGIN IF 子结点符合条件 THEN BEGIN 5 OPEN：=OPEN+1；把新结点存入队列；IF 新结点与原有结点重复 THEN OPEN：=OPEN-1删去刻结点 ELSE IF 新结点是目标结点 THEN BEGIN 输出结果并退出；END；END；END；UNTIL CLOSEDOPEN队列空(三)算法特性 1、空间复杂度 因为所有节点都必须被储存，因此广度优先搜索算法的空间复杂度为 O(|V|+|E|)，其中|V|是节点的数目，而|E|是图中边的数目。注：另一种说法称广度优先搜索算法的空间复杂度为 O(BM)，其中 B 是最大分支系数，而 M 是树的最长路径长度。由于对空间的大量需求，因此广度优先搜索算法并不适合解非常大的问题。2、时间复杂度 最差情形下，广度优先搜索算法必须寻找所有到可能节点的所有路径，因此其时间复杂度为 O(|V|+|E|)，其中|V|是节点的数目，而|E|是图中边的数目。3、完全性 广度优先搜索算法具有完全性。这里指无论图形的种类如何，只 6 要目标存在，则广度优先搜索算法一定会找到。然而，若目标不存在，且图为无限大，则广度优先搜索算法将不收敛（不会结束）。4、最佳解 若所有边的长度相等，广度优先搜索算法是最佳解亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，广度优先搜索算法并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，广度优先搜索算法仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，广度优先搜索算法的改良算法成本一致搜寻法（en:uniform-cost search）来解决。然而，若非加权图形，则所有边的长度相等，广度优先搜索算法就能找到最近的最佳解。(四)广度优先搜索算法在图论中的应用 寻找图中所有连接元件（Connected Component）。一个连接元件是图中的最大相连子图。寻找连接元件中的所有节点。寻找非加权图中任两点的最短路径。测试一图是否为二分图。(Reverse)CuthillMcKee 算法。7 三、广度优先搜索算法在图论中应用的具体分析(一)寻找连接元件 由起点开始，执行广度优先搜索算法后所经过的所有节点，即为包含起点的一个连接元件。(二)测试是否二分图 广度优先搜索算法可以用以测试二分图。从任一节点开始搜寻，并在搜寻过程中给节点不同的标签。例如，给开始点标签 0，开始点的所有邻居标签 1，开始点所有邻居的邻居标签二以此类推。若在搜寻过程中，任一节点有跟其相同标签的邻居，则此图就不是二分图。若搜寻结束时这种情形未发生，则此图为一二分图。(三)寻找非加权图中任两点的最短路径 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。最短路的定义：在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数 W:ER 为从边到实型权值的映射。路径 P=(0v,1v,kv)的权是指其组成边的所有权值之和：11()(,)kiiiw pw vv 定义 u 到 v 间最短路径的权为：8 min():(,)w p 存在由 到 的通路存在 从结点 u 到结点 v 的最短路径定义为权()w pv 的任何路径。广度优先搜索能够在非加权图G=(V,E)中快速地寻找从一个固定顶点 s 到其余顶点之间的最短距离。广度优先搜索是基于如下的简单想法：从 s 点开始，访问每一个被 s 支配的顶点 x。设(,)1dist s x 和:()spred x（顶点 s 是 x 的前驱）。访问哪些与 s 距离不为 1 且受 x 所支配的顶点 y，则有(,):2:()dist s yxpred y和。继续这种过程，直至达到所有能达到的顶点。这些顶点是从 s 点可达的。由于搜索过程是一级一级展开的，因此能快速的找到 s 点到其能到达的顶点的最短路径。对于那些不能从 s 点可达的剩余顶点 z，令(,):dist s z 。广度优先搜索较为正式的表述是算法的结尾处，():pred vnil意味着vs或者v 从 s 是不可达的。（附件中有用 matlab 语言实现最短路径搜索算法的程序）。实作方法 1、首先将根节点放入队列中。2、从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。3、若队列为空，表示整张图都检查过了亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。4、重复步骤 2。9 四、最短路中常用算法的比较 其它最短路算法与广度优先搜索算法的比较列表 算法 时间复杂度 空间复杂度 编程复杂度 适用范围 BFS O(E+V)O(E+V)简单 非加权图（窄）Dijkstra O(2V)或O(E+V)logV)O(2V)或 O（E+V）简单或相对复杂 不含负权的图（窄）Floyd O（3N）O（2N）简单 实数图（广）Bellman-Ford O（VE）O(E+V)简单 实数图（广）SPFA O(E)O(E+V)简单 实数图（广）通过比较分析分析，可知：对于非加权图，可用简便而又快捷的广度优先搜索算法找出最短路径。Dijkstra 算法的效率高，但是也有局限性，就是对于含负权的图无能为力。Floyd 算法简单、易于实现，且适用范围广，但时间和空间复杂度过高。Bellman-Ford算法对于所有最短路长存在的图都适用而且简单，但是时间复杂度高，效率常常不尽人意。SPFA 算法可以说是综合了上述算法的优点。它的效率同样很不错，而且对于最短路中存在的所有图都适用，无论是否存在负权。它的编程复杂度也很低，是高性价比的算法。10 五、总结 广度优先搜索算法是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。广度优先搜索算法并不使用经验法则算法。对于非加权图，广度优先搜索算法可以快速的找出最短路径（假设存在最短路径），但其在最短路问题中的适用范围较窄。当最短路问题中出现赋权边或负权时，可以根据情况选择Dijkstra、Floyd、Bellman-Ford 和 SPFA 等算法搜索最短路。对于寻找图中所有连接元件，广度优先搜索是一种快速简便的方法。另外，广度优先搜索算法还可以用于测试二分图。因此广度搜索算法在图论中有广泛的应用。对广度优先算法加以改进，可以得到特性更好的算法，如，双向广度优先搜索算法和*A算法等。附件 Matlab 程序：function R,T=bfs(A,s,d)%A：邻接矩阵(连通点间的距离为1，不连通的点间距离为inf,同点间距离为0）%s：源顶点，d：目标顶点%R：搜索过的节点%T：搜索过的边%k=s;R(1)=s;Q(1)=s;T=;qq=;11 kk=0;while size(Q)%从Q中选一点%选最先插入 Q的点%p,q=find(A(k,:)=1)qq=qq,q;for i=1:size(q)if sum(find(R=q(i)a=find(Q=q(i);Q(a)=;else Q=Q,q(i);R=R,q(i);T=T;k,q(i);end if i=d break;end end if i=d break;end k=qq(kk+1);end if sum(size(Q)=0 disp(找不到目标。);end 开场白 许多学生认为数学是枯燥的、乏味的。一些非数学老师在听完一堂数学课后，往往这样评价：思路清晰、语言精练、解题严谨，就是太乏味、缺少趣味性，让人昏昏欲睡。那么，如何调动学生的上课积极性，引发他们的好奇心？设计好“开场白”，非常关键。下面是数学课的几个片断：动手实验式“开场白”：桌上摆满了切成各种形状的萝卜，大伙好像还在热列地讨论着什么。老师微笑问：“同学们，用一个平面去截一个正方体，截出的面可能是什么形状？”悬念式“开场白”：老师一上讲台，故意神神秘秘地说“你们每人随便想一个自然数，将这个数乘5减7，再把结果乘2加14”。“你们算得的结果个位数字一定是0”。顿时教室里象炸了锅似的，“等你学了字母表示数，你也会算了”。12 故事式“开场白”：为了让学生体会图形的边长、周长、面积在变化过程中的关系，领会列方程解应用题时，关键是捕捉到不变的量。老师先给学生讲了一个故事：父亲的羊越来越多，想拆旧羊圈扩大面积，可是没有多余的篱笆，怎么办呢？他叫来了儿子,儿子不慌不忙地说：“爸，我有办法”。“你看，旧羊圈长70米，宽30米，面积2100平方米。如果改成50米见方的新羊圈，不用添篱笆，羊圈面积就有2500平方米”。诸如此类的还有：“贴近生活式”开场白；“设疑式”开场白；“名言式”开场白；“趣味式”开场白；“实例式”开场白；“比喻式”开场白等等。向学生提出恰当的问题，激发起学生的兴趣，提高他们学习的积极性。