廣度優先演算法

『壹』 深度優先和廣度優先 的區別 ，用法。

1、主體區別

深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件)。

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。

2、演算法區別

深度優先搜索是每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

廣度優先搜索是每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅，找到所要找的元素時結束程序。

3、用法

廣度優先屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

深度優先即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。

(1)廣度優先演算法擴展閱讀：

實際應用

BFS在求解最短路徑或者最短步數上有很多的應用，應用最多的是在走迷宮上，單獨寫代碼有點泛化，取來自九度1335闖迷宮一例說明，並給出C++/Java的具體實現。

在一個n*n的矩陣里走，從原點（0,0）開始走到終點（n-1,n-1），只能上下左右4個方向走，只能在給定的矩陣里走，求最短步數。n*n是01矩陣，0代表該格子沒有障礙，為1表示有障礙物。

int mazeArr[maxn][maxn]; //表示的是01矩陣int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4個方向，int visit[maxn][maxn]; //表示該點是否被訪問過，防止回溯，回溯很耗時。核心代碼。基本上所有的BFS問題都可以使用類似的代碼來解決。

『貳』 深度優先演算法 和 寬度優先演算法 的優缺點

1、深度優先演算法佔內存少但速度較慢，廣度優先演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。
2、深度優先與廣度優先的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。
3、這兩種演算法每次都擴展一個節點的所有子節點，而不同的是，深度優先下一次擴展的是本次擴展出來的子節點中的一個，而廣度優先擴展的則是本次擴展的節點的兄弟點。在具體實現上為了提高效率,所以採用了不同的數據結構。

『叄』 廣度優先遍歷的演算法

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

『肆』 廣度優先演算法的簡介

由圖一可以知道，這樣形成的一棵樹叫搜索樹。初始狀態對應著根結點，目標狀態對應著目標結點。排在前的結點叫父結點，其後的結點叫子結點，同一層中的結點是兄弟結點，由父結點產生子結點叫擴展。完成搜索的過程就是找到一條從根結點到目標結點的路徑，找出一個最優的解。這種搜索演算法的實現類似於圖或樹的遍歷，通常可以有兩種不同的實現方法，即深度優先搜索（DFS——Depth First search）和廣度優先搜索（BFS——Breadth First Search）。

『伍』 廣度優先 演算法，各位幫幫。。急

個人對廣度優先演算法的理解是每次優先遍歷父結點下的直接子結點，遍歷完這些直接子結點之後再從這些子結點開始遍歷他們的直接子結點，以此類推下去，直到找到終點。所以，此處肯定是需要使用到迭代了。在此我想寫出我的思路來與樓主交流下。
1.確定startway點和endway點以後，找到startway點，並對該點下的子結點進行遍歷。如你此處選擇的startway是牧野草原04 即位置在ab(04)，endway是牧野草原15，那麼ab(04)下的直接子結點可認為是牧野草原06、牧野草原08和牧野草原10。我們開始按照廣度優先演算法遍歷到牧野草原15。
2.首先我們遍歷完04的子結點（06，08，10），發現沒有15。
3.接下來我們遍歷結點06的子結點（04，05，03），發現沒有15.
4.然後，我們開始遍歷結點08的子結點（4，15，16），發現15，於是整個遍歷結束。
PS:對於迴路的子結點不應該考慮遍歷，比如06中04的迴路。

『陸』 怎樣理解深度優先演算法和廣度優先演算法

胡說八道.... 深度優先:前序遍歷 廣度優先:按層遍歷

『柒』 廣度優先演算法（寬搜）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屬性，可保萬無一失
希望對你有幫助~

『捌』 廣度優先搜索演算法

我以前做的一個光搜題，給你貼上吧，是一個關於素數變化的題目，輸入一對素數，每個是4位數，每次只能變化一位數，且變化後的數還是素數，求經過多少次變化，能變成另一個輸入的素數。程序有點復雜，慢慢看吧。

#include<iostream>

#include<cmath>

usingnamespacestd;

inttemp,temp2,i,j;

intf(intt)

{

temp2=sqrt(float(t))+1;

for(j=2;j<temp2;++j)

if(t%j==0)

return0;

return1;

}

intmain()

{

intprime[10000],qu[20000],result,k,h,num,tag[10000],sum,index,itag,d[10000],atag;

while(1)

{

for(i=1000;i<10000;++i){tag[i]=0,d[i]=0;}

cin>>num>>result;

k=0;h=1;qu[k]=num;index=0;itag=1;tag[num]=1;atag=0;

while(k!=h)

{

if(qu[k]==result)

{cout<<d[qu[k]]<<endl;break;}

if(qu[k]%2==0)continue;

temp=qu[k]-qu[k]%10+1;

for(i=0;i<5;i++,temp+=2)

if(f(temp)==1&&tag[temp]==0)

{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;

if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;

temp=qu[k]-qu[k]%100/10*10;

for(i=0;i<10;++i,temp+=10)

if(f(temp)==1&&tag[temp]==0)

{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;

if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;

temp=qu[k]-qu[k]%1000/100*100;

for(i=0;i<10;++i,temp+=100)

if(f(temp)==1&&tag[temp]==0)

{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;

if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;

temp=qu[k]-qu[k]/1000*1000+1000;

for(i=0;i<8;++i,temp+=1000)

if(f(temp)==1&&tag[temp]==0)

{tag[temp]=1;d[temp]=d[qu[k]]+1;qu[h]=temp;

if(temp==result){cout<<d[temp]<<endl;atag=1;break;}++h;}if(atag==1)break;

++k;

}

}

return1;

}

『玖』 廣度優先法(BFS)演算法

#include<stdio.h>#define MAX 10 int front=-1,rear=-1; struct node { int value; struct node *next; }; typedef struct node node; typedef node *link; struct graph_link { link first; //隊頭指針 link last; //隊尾指針 }; int run[9]={0}; int queue[MAX]; struct graph_link head[9]; void print(struct graph_link temp) { link current=temp.first; while (current!=NULL) { printf("[%d] ",current->value); current=current->next; } putchar('\n'); } void insert(struct graph_link *temp, int x) //鄰接表法存儲頂點 { link new_node; new_node=new node; new_node->value=x; new_node->next=NULL; if (temp->first==NULL) { temp->first=new_node; //新隊頭 temp->last=new_node; //當前尾指向頭 } else { temp->last->next=new_node; //原隊尾的結點接上新結點 temp->last=new_node; //將隊尾結點指向新結點 } } void enqueue(int value) //入隊 { if (rear>=MAX) return; queue[rear++]=value; } int dequeue() //出隊 { if (front==rear) return -1; front++; return queue[front]; } void bfs(int current) //廣度優先 { link tempnode; enqueue(current); //入隊 run[current]=1; printf("[%d] ",current); while (front!=rear) //判斷是否為空隊列 { current=dequeue(); //出隊 tempnode=head[current].first; //與i個頂點的鏈表頭指針 while (tempnode!=NULL) { if (run[tempnode->value]==0) //判斷以i個頂點連接的頂點是否被訪問過 { enqueue(tempnode->value); //入隊 run[tempnode->value]=1; //標記已訪問過 printf("[%d] ",tempnode->value); } tempnode=tempnode->next; } } } void main() { int data[20][2]={{1,2},{2,1},{1,3},{3,1},{2,4},{4,2}, {2,5},{5,2},{3,6},{6,3},{3,7},{7,3}, {4,5},{5,4},{6,7},{7,6},{5,8},{8,5}, {6,8},{8,6}}; int data_num,i,j; for (i=1; i<9; i++) { head[i].first=NULL; head[i].last=NULL; for (j=0; j<20; j++) { if (data[j][0]==i) { data_num=data[j][1]; insert(&head[i],data_num); } } } printf("Imgae Data:\n"); for (i=1; i<9; i++) { printf("peak[%d]=> ",i); link ptr=head[i].first; while (ptr!=NULL) { printf("[%d] ",ptr->value); ptr=ptr->next; } putchar('\n'); } putchar('\n'); bfs(1); putchar('\n'); }

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