广度优先算法毕业论文百度文库

深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。 一、深度优先搜索         深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 基本步奏 （1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。 （2）从stack中访问栈顶的点； （3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行； （4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。二、广度优先搜索         广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。 基本步奏 （1）给出一连通图，如图，初始化全是白色（未访问）； （2）搜索起点V1（灰色）； （3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）； （4）对V2，V3，V4重复以上操作； （5）直到终点V7被染灰，终止； （6）最短路径为V1，V4，V7.

1、定义

广度优先搜索 （Breadth-First Search）是最简便的图的搜索算法之一，又称 宽度优先搜索 ，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

2、应用

广度优先搜索被用于解决 最短路径问题（shortest-path problem） 。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

3、图简介

既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。

图由 节点 和 边 组成。一个节点可能与多个节点相连，这些节点被称为邻居。

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。

例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：

而使用广度优先搜索工作原理大概如下 ：

1、Python 3 ：

2、PHP ：

1、《算法图解》 2、SplQueue类：