廣度優先搜索遍歷的演算法步驟

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)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。