广度优先搜索遍历的算法步骤

1. 已知一个有向图如图，请分别写出从顶点a出发进行深度优先遍历和广度优先遍历所得到的顶点序列及生成树。

一、深度生成树：abdcefigh，如下图所示：

相关特点：

（1）生成树协议提供一种控制环路的方法。采用这种方法，在连接发生问题的时候，你控制的以太网能够绕过出现故障的连接。

（2）生成树中的根桥是一个逻辑的中心，并且监视整个网络的通信。最好不要依靠设备的自动选择去挑选哪一个网桥会成为根桥。

（3）生成树协议重新计算是繁冗的。恰当地设置主机连接端口(这样就不会引起重新计算)，推荐使用快速生成树协议。

（4）生成树协议可以有效的抑制广播风暴。开启生成树协议后抑制广播风暴，网络将会更加稳定，可靠性、安全性会大大增强。

2. 关于广度优先搜索算法

广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。

这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！

如下是一段迷宫的最佳路径求解算法。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

3. 图的矩阵深度和广度遍历算法

图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。
图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1，V2和V3之后，有可能沿着边（V3，V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空
集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
从图G=（V，E）的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
例25.(p194.c)图的深度优先搜索。从图G的顶点V0
发进行深度优先搜索，打印出各个顶点的遍历顺序。
解：图的深度优先搜索法为：
（1）首先访问V0并把V0加到集合visited中；
（2）找到与V0相邻的顶点W，若W未进入
visited中，则以深度优先方法从W开始搜索。
（3）重复过程（2）直到所有于V0相邻的顶点
都被访问过为止。

下面是对用邻接表表示的图G进行深度优先搜索的程序
int rear=0; /*Visit和rear都为全局变量*/
int visit[500];
depth_first_search(g,v0) /*从V0开始对图G进行深度
优先搜索*/
graphptr g[ ]; /*指针数组,为邻接表表头顶点指针
g[vi]...g[vn]*/
int v0; /*这里V0和W都是顶点标号,如V0=0或1*/
{ /*g[v0]是顶点V0的表头指针*/
int w;
graphptr p; /*链表的结点指针*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一个顶点，通过邻接表表头指针
，访问v0的邻接顶点*/
while (p!=NULL)
{
w=p->vertex ;/*这里W是与V0相邻的一个顶点*/
if (!visited(w))/*当V0的相邻结点，W未被访问时，从W开始遍厉*/
depth_first_search(g,w);
p=p->next;/*接着访问另一个相邻顶点*/
}
}
int visited(w) /*检查顶点w是否进入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，说明被访问过*/
return(0); /*W不在visit[]中，说明未被访问过，返回0*/
}
2）图的广度优先搜索
从图G的一个顶点V0出发，依次访问V0的邻接点K1,K2...Kn。然后再顺序访问K1,K2...Kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从V1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
（1）首先把V0放入队列；
（2）若队列为空则结束，否则取出队列的头V；
（3）访问V并把所有与V相邻且未被访问的顶点插入队列；
（4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
广度搜索法的程序如下：
broad_first_search(g,v0) /*从V0开始对图g进行广度优先搜索*/
graphptr g[ ]; /*为邻接表，表头顶点指针*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入队列queue*/
while (front <=tail)/*当队列不为空*/
{
v=queue[front++]; /*取出队列中的顶点*/
printf("%d\n",v); /*访问该顶点*/
p=g[v]; /*从顶点V的链表来考虑与V相邻的顶点*/
while (p!=NULL)
{
v=p->vertex; /*从第一个结点（即边）中找出相邻的顶点*/
if (!visited(queue,tail,v))/*判断顶点是否进入队列，如进入队列
说明已被访问或将要访问*/
queue[++tail]=v;/*如果该顶点未被访问过，将此相邻顶点插入队列*/
p=p-->next;/*再考虑该结点的下一个相邻顶点*/
}
}
}
visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/
int q[ ],tail,v;/*进入队列的顶点，在front之前的顶点已被访问过打印输出，
在front和tail之间的顶点是即将要访问顶点*/
{
int i;
for(i=1;i<=tail;i++)/*扫描队列，确定v是否在队列中，在队列中返回1，否则返回0*
/
if (q[i]==v)return(1);/*队列中的顶点都认为已被访问过*/
return(0);
}

深度优先的非递归算法

/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())

{
p=stackMain.pop();

}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.

{

visit(p);

p.marked=true;

}

}while(!stackMain.isEmpty())

4. 用邻接表表示图的广度优先搜索时的存储结构,通常采用（）结构来实现算法

B。

广度优先搜索相当于层次遍历，深度优先搜索相当于先序优先遍历，所以答案选择B。

邻接表表示的图的广度优先搜索一般采用队列结构来实现算法：

首先选择一个起始节点，把它的临界表中节点加入到队列中，每次取出队首元素，然后把该元素的邻接表中的节点加入到队列末尾，标记已遍历过的节点，直到队列中没有节点为止，一般栈用于深度优先搜索，队列用于广度优先搜索。

(4)广度优先搜索遍历的算法步骤扩展阅读：

深度优先搜索用一个数组存放产生的所有状态。

（1） 把初始状态放入数组中，设为当前状态；

（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；

（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；

（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。

5. 广度优先搜索C语言算法

广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。

这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！

如下是一段迷宫的最佳路径求解算法。
#include <stdio.h>

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

6. 简述深度优先搜索遍历的方法。

简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

思路
假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。


首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1->2->4->5->3->6->7

那是怎样得到这样的结果呢？
根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再选定新的分支。

定义节点

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式

分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真的懂递归吗？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。

但是为了保证出栈的顺序，需要先压入右节点，再压左节点。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接着再列举个利用深度优先遍历的方式的题目

扫雷
给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。

根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例

输入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。

注意 ：



在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。

7. 广度优先遍历是什么

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是图中顶点的数目），用来记录每个顶点是否已被访问过。

8. 广度优先遍历的算法

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(队列空)

9. 广度优先算法

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

10. 深度优先搜索遍历和广度优先搜索的遍历序列及具体步骤和原因，

1->2->3->4 （表示1可达到2，达到3，达到4）

2->1->3->5

3->1->2->4->5->6

4->1->3->6

5->2->3->6

6->3->4->5

广度优先搜索就是把每一行按照顺序输出，去掉重复的，即先看1，有1,2,3,4，然后看2，因为有3,4了，所以只要5，然后看3，以此类推。。一行行来。

深度优先搜索，是先看1，然后1可以到2，然后直接看2,2可以到3,5随便选一个都可以，我们到3好了，然后看3的那行可以到1,2,4,5,6随便选一个都可以，不过要去掉重复的，以此类推。可以排出很多种的。

(10)广度优先搜索遍历的算法步骤扩展阅读：

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。

若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。