广度优先算法

‘壹’ 深度优先和广度优先 的区别 ，用法。

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;
}