廣度優先演算法實現

『壹』 急！！C++深度優先演算法和廣度優先演算法

以搜索為例，下面兩種介紹了深搜與廣搜的具體實現。
演算法博大精深，望樓主好好學習啊
1. 深度搜索
void Graph::DFS(const int v, int visited[])
{
cout<<GetValue(v)<<"";//訪問頂點 v
visited[v] = 1; //頂點 v 作訪問標記
int w = GetFirstNeighbor(v););//取 v 的第一個鄰接頂點 w
while(w != -1) //若鄰接頂點 w 存在
{
if(!visited[w])//若頂點 w 未訪問過, 遞歸訪問頂點 w
DFS(w, visited);
w = GetNextNeighbor(v, w);//取頂點 v 的排在 w 後面的下一個鄰接頂點
}
}
void Graph::UseDFS()
{
visited = new Boolean[n];
for(int i = 0; i < n; i++)
visited[i] = 0;
DFS(0);
delete[] visited;
}
演算法分析：
(1)圖中有 n 個頂點，e 條邊。
(2)如果用鄰接表表示圖，沿 link 鏈可以找到某個頂點 v 的所有鄰接頂點 w。由於總共有 2e 個邊結點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復雜性為O(n+e)。
(3)如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。
2. 廣度優先搜索
void BFS(Graph G, int visited[])
{//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.
for(v = 0; v < G.vexnum; v++)
visited[v] = false;
Quene q;
for(v = 0; v < G.vexnum; v++)
if(!visited[v])
{
visited[v] = true;
EnQuene(Q,v);
while(!QueneEmpty(Q))
{
DeQuene(Q,u);
for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
if(!visited[w])
{
visited[w] = true;
EnQuene(Q, w);
}//if
}//while
}//if
}//BFS
演算法分析：
每個頂點至多進一次隊列。遍歷圖的過程實質上是通過邊或弧找鄰接點的過程，因此廣度優先搜索遍歷圖的時間復雜度和深搜相同。

『貳』 基本演算法——深度優先搜索（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.

『叄』 用鄰接表表示圖的廣度優先搜索時的存儲結構,通常採用（）結構來實現演算法

B。

廣度優先搜索相當於層次遍歷，深度優先搜索相當於先序優先遍歷，所以答案選擇B。

鄰接表表示的圖的廣度優先搜索一般採用隊列結構來實現演算法：

首先選擇一個起始節點，把它的臨界表中節點加入到隊列中，每次取出隊首元素，然後把該元素的鄰接表中的節點加入到隊列末尾，標記已遍歷過的節點，直到隊列中沒有節點為止，一般棧用於深度優先搜索，隊列用於廣度優先搜索。

(3)廣度優先演算法實現擴展閱讀：

深度優先搜索用一個數組存放產生的所有狀態。

（1） 把初始狀態放入數組中，設為當前狀態；

（2） 擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態；

（3） 判斷當前狀態是否和前面的重復，如果重復則回到上一個狀態，產生它的另一狀態；

（4） 判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束演算法。

『肆』 廣度優先搜索有什麼難點

廣度優先搜索難點在於每一種演算法的不同，樹的遍歷。

擴展知識：

廣度優先搜索演算法又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。

廣度優先搜索演算法主要有四個特性：

空間復雜度：由於對空間的大量需求，因此BFS並不適合解非常大的問題，對於類似的問題，應用IDDFS已達節省空間的效果。

時間復雜度：最差情形下，BFS必須查找所有到可能節點的所有路徑。

完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。

最佳解：若所有邊的長度相等，廣度優先搜索演算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。

『伍』 廣度優先演算法（寬搜）pascal

下面是一段delphi代碼：
演算法核心代碼，為增強演算法通用性，將窗體的一個treeview和ADOQuery引用到局部變數中，作為對象引用，不創建，也不釋放，相當於別名
procere Tfrm.FmtTree();
var
i,j :integer;
leafList,leafListPlus: TList;
leaf,subNode: TTreeNode;
tv: TTreeView;//引用窗體控制項
qry: TADOQuery;//引用窗體控制項
begin
//初始化
leafList:=TList.Create;
leafListPlus:=TList.Create;
tv:=tvw1;
tv.Items.Clear;
qry:=qry1;
subNode:=tv.Items.AddChild(nil,'月夜風箏(我)的公司');
leafList.Add(subNode);
//處理
while leafList.Count > 0 do
begin
leafListPlus.Clear;
for i:=0 to leafList.Count-1 do
begin
leaf:=leafList[i];
if leaf.Level = 0 then
qry.SQL.Text:=Format('select code,name,belong from TB where belong = ''%s''',['--'])
else
qry.SQL.Text:=Format('select code,Name,belong from TB where belong = ''%d''',[leaf.StateIndex]);
qry.Open;
for j:= 0 to qry.RecordCount-1 do
begin
subNode:=tv.Items.AddChild(leaf,qry.FieldByName('name').AsString);
subNode.ImageIndex:=subNode.Level;
subNode.StateIndex:=StrToInt(qry.FieldByName('code').AsString);
leafListPlus.Add(subNode);
qry.Next;
end;
end;
leafList.Assign(leafListPlus);
end;
//清理
tv.FullExpand;
leafListPlus.Free;
leafList.Free;
end;

說明：
用TList類型模擬實現了廣度優先演算法的隊列－－先進先出－－實際上，本演算法不需要那麼嚴格，只要按批先進先出就行了。leafList用於當前循環，leafListPlus用於下一輪循環，其中保存的都是樹節點類型，以方便在treeview上直接插入子節點，就省了查找父結點的演算法，節點的編號緩存在節點的StateIndex屬性中，編號可轉為整數型這是最方便的，如果編號不能保證可轉為整數，可以使用data屬性，可保萬無一失
希望對你有幫助~

『陸』 廣度優先搜索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;
}

『柒』 常見演算法5、廣度優先搜索 Breadth-First Search

1、定義

廣度優先搜索 （Breadth-First Search）是最簡便的圖的搜索演算法之一，又稱 寬度優先搜索 ，這一演算法也是很多重要的圖演算法的原型。廣度優先搜索屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

2、應用

廣度優先搜索被用於解決 最短路徑問題（shortest-path problem） 。

廣度優先搜索讓你能夠找出兩樣東西之間的最短距離，不過最短距離的含義有很多！使用廣度優先搜索可以：

3、圖簡介

既然廣度優先搜索是作用於圖的一種演算法，這里對圖作一個簡單的介紹，先不深入了解。

圖由 節點 和 邊 組成。一個節點可能與多個節點相連，這些節點被稱為鄰居。

廣度優先演算法的核心思想是：從初始節點開始，應用算符生成第一層節點，檢查目標節點是否在這些後繼節點中，若沒有，再用產生式規則將所有第一層的節點逐一擴展，得到第二層節點，並逐一檢查第二層節點中是否包含目標節點。若沒有，再用算符逐一擴展第二層的所有節點……，如此依次擴展，檢查下去，直到發現目標節點為止。即

廣度優先搜索使用隊列（queue）來實現，整個過程也可以看做一個倒立的樹形。

例：假如你需要在你的人際關系網中尋找是否有職業為醫生的人，圖如下：

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

1、Python 3 ：

2、php ：

1、《演算法圖解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue類： https://www.php.net/manual/zh/class.splqueue.php