广度优先遍历的算法

‘壹’ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为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.广度优先遍历的思想广度优先遍历类似树的按层次遍历。设初始状态时图中的所有顶点未被访问，则算法思想为：首先访问图中某指定的起始顶点v，并将其标记为已访问过，然后由v出发依次访问v的各个未被访问的邻接点v1，v2，…，vk；并将其均标识为已访问过，再分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v路径相通的顶点都被访问到。

若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述搜索过程，直至图G中所有顶点均被访问为止。

2.广度优先遍历示例例如，对图7－18（a）所示的图G，假设指定从顶点v1开始进行广度优先遍历，首先访问v1，因与v1相邻并且未被访问过的顶点有v2和v6，则访问v2和v6，然后访问与v2相邻并未访问的邻接点v2，v7，再访问与v6相邻并且未被访问过的邻接点v5，按这样的次序依次访问与v2相邻并且未被访问过的邻接点v4，v8，与v7相邻并且未被访问过的邻接点v9，此时，与v5，v4，v8，v9相邻并且未被访问过的邻接点没有了，即图G中的所有顶点访问完，其遍历序列为：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。这种顺序不是唯一的，如果从v1出发后，相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，图7－18（b）是假设从v1开始，相邻的多个顶点优先选择序号小的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。图7－18（c）假设从a开始，相邻的多个顶点优先选择ASCII码小的顶点访问，其遍历序列为：a－＞b－＞d－＞e－＞f－＞c－＞g；相邻的多个顶点优先选择ASCII码大的顶点访问，其遍历序列为：a－＞f－＞e－＞d－＞b－＞g－＞c。

2.广度优先遍历的算法在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点的访问顺序，将访问的每个顶点入队，然后再依次出队。

在广度优先遍历过程中，为了避免重复访问某个顶点，也需要创建一个一维数组visited［n］（n是图中顶点的数目），用来记录每个顶点是否已被访问过。

‘叁’ 广度优先算法

广度优先算法（Breadth-First Search），同广度优先搜索，又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。

‘肆’ 广度优先遍历的算法

template <int max_size>
void Digraph<max_size> ::
breadth_first(void (*visit)(Vertex &)) const
/* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order.
Uses: Methods of class Queue. */
{
Queue q;
bool visited [max_size];
Vertex v, w, x;
for (all v in G) visited [v] = false;
for (all v in G)
if (!visited [v]) {
q.append (v);
while (!q.empty ( )){
q.retrieve (w);
if (!visited [w]) {
visited [w] = true; (*visit) (w);
for (all x adjacent to w) q.append (x); }
q.serve ( ); } }
}
广度优先搜索算法pascal 算法框架
Program BFS;
初始化，存储初始状态（记录初始结点）；
设队列首指针closed=0；队列尾指针open：=1；
repeat
首指针closed后移一格，取其所指向的结点；
for r:=1 to max_r do
begin
if子结点符合条件 且 子结点没有重复扩展 then
begin
尾指针open加1；把新结点存入队列尾；
记录相关信息；
if 达到目标 then 输出且结束；
end;
until closed>=open(队列空)

‘伍’ 深度优先遍历与广度优先遍历的区别

一、指代不同

1、深度优先遍历：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

2、广度优先遍历：系统地展开并检查图中的所有节点，以找寻结果。

二、特点不同

1、深度优先遍历：所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。

2、广度优先遍历：并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

三、算法不同

1、深度优先遍历：把根节点压入栈中。每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。

2、广度优先遍历：把根节点放到队列的末尾。每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。

‘陆’ 图的遍历方法主要包括

图的遍历方法主要包括深度优先搜索法和广度（宽度）优先搜索法两种算法。

广度优先遍历（Breadth First Search），又称为广度优先搜索，简称BFS。深度优化遍历(Depth First Search)，也有称为深度优化搜索，简称为DFS。事实上，我们在树的遍历中早已涉及DFS，层序遍历、中序遍历和后序遍历都属于深度优先遍历的方式，因为这些遍历方式本质上都归结于栈。

图的遍历方法复杂性介绍

① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。

② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。

③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。

④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。

‘柒’ JS 深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历DFS

自定义：深度单线游走，从根走完最后一个节点，在游走兄弟节点，走完兄弟的所有子节点，循环之。

 银高返    递归算法：

function deepFirstSearch(node, nodeList = []) {

  if (node) {

    nodeList.push(node);

    var children = node.children;

    for (var i = 0; i < children.length; i++)

      //每次递归的时候将 需要遍历的节点 和 节点所存储的数组传下去

      deepFirstSearch(children[i], nodeList);

  }

  return nodeList;

}

非递归算法：

function deepFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var stack = [];

    stack.push(node);

    while (stack.length != 0) {

      var item = stack.pop();

      nodes.push(item);

      var children = item.children;

      for (var i = children.length - 1; i >= 0; i--)

        stack.push(children[i]);

    }

  }

  return nodes;

}

广度优先遍历(BFS)

自定义：从根开始 层层推进 走完一层 走下一层 （犹如爬楼，走完一层的楼梯，继续下一层的楼梯）

递锋饥归算法：（容易念森栈溢出）

function breadthFirstSearch(node) {

  var nodes = [];

  var i = 0;

  if (!(node == null)) {

    nodes.push(node);

    breadthFirstSearch(node.nextElementSibling);

    node = nodes[i++];

    breadthFirstSearch(node.firstElementChild);

  }

  return nodes;

}

非递归算法：（推荐）

function breadthFirstSearch(node) {

  var nodes = [];

  if (node != null) {

    var queue = [];

    queue.unshift(node);

    while (queue.length != 0) {

      var item = queue.shift();

      nodes.push(item);

      var children = item.children;

      for (var i = 0; i < children.length; i++)

        queue.push(children[i]);

    }

  }

  return nodes;

}