广度优先搜索算法
Ⅰ 广度优先搜索算法，请给出简单的c++程序样例
#include <stdio.h>
#define max 100
typedef struct anode
{
int adjvex; //边的终点位置
struct anode *nextarc;
}arcnode;
typedef struct node
{
int data;
arcnode *firstout;
}vnode;
typedef struct
{
vnode adjlist[max];
int n;
int e;
}Agraph;
static int visit[max];
//深度遍历
void DFS(Agraph &G,int v) //v为初始顶点编号
{
int k;
arcnode *p;
for(k=0;k<G.n;k++)
visit[k]=0;
printf("%d ",v);
p=G.adjlist[v].firstout;
while(p)
{
if(!visit[p->adjvex])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
void BFS(Agraph &G,int v)
{
arcnode *p;
int q[max];
int front=0;
int rear=0;
int w,i;
for(i=0;i<G.n;i++)
visit[i]=0;
printf("%d ",v);
visit[v]=1;
rear=(rear+1)%max;
q[rear]=v;
while(front!=rear)
{
front=(front+1)%max;
w=q[front];
p=G.adjlist[w].firstout;
while(p)
{
if(!visit[p->adjvex])
{
printf("%d ",p->adjvex);
visit[p->adjvex]=1;
rear=(rear+1)%max;
q[rear]=p->adjvex;
}
p=p->nextarc;
}
printf("\n");
}
}
//层序遍历二叉树
struct btnode
{
int data;
btnode *lchild,*rchild;
};
void level(struct btnode *bt)
{
if(!bt)
return;
btnode *q[max];
int front,rear;
front=0;
rear=0;
printf("%d ",bt->data);
rear=(rear+1)%max;
q[rear]=bt;
while(front!=rear)
{
front=(front+1)%max;
bt=q[front];
if(bt->lchild)
{
printf("%d ",bt->lchild->data);
rear=(rear+1)%max;
q[rear]=bt->lchild;
}
if(bt->rchild)
{
printf("%d ",bt->rchild->data);
rear=(rear+1)%max;
q[rear]=bt->rchild;
}
}
}
void DFS1(Agraph &G,int v)
{
arcnode *p;
printf("%d ",v);
visit[v]=1;
p=G.adjlist[v].firstout;
while(p)
{
if(!visit[p->adjvex])
{
DFS1(G,p->adjvex);
}
p=p->nextarc;
}
}
void level1(struct btnode *bt)
{
if(!bt)
return;
printf("%d ",bt->data);
struct btnode *q[max];
int front=0;
int rear=0;
rear=(rear+1)%max;
q[rear]=bt;
while(front!=rear)
{
front=(front+1)%max;
bt=q[front];
if(bt->lchild)
{
printf("%d ",bt->lchild->data);
rear=(rear+1)%max;
q[rear]=bt->lchild;
}
if(bt->rchild)
{
printf("%d ",bt->rchild->data);
rear=(rear+1)%max;
q[rear]=bt->rchild;
}
}
}
void BFS1(Agraph &G,int v)
{
int q[max];
int front=0;
int rear=0;
int i;
for(i=0;i<G.n;i++)
visit[i]=0;
printf("%d ",v);
visit[v]=1;
rear=(rear+1)%max;
q[rear]=v;
arcnode *p;
while(front!=rear)
{
front=(front+1)%max;
i=q[front];
p=G.adjlist[i].firstout;
while(p)
{
if(!visit[p->adjvex])
{
printf("%d ",p->adjvex);
visit[p->adjvex]=1;
rear=(rear+1)%max;
q[rear]=p->adjvex;
}
p=p->nextarc;
}
}
}
Ⅱ 广度优先法(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'); }
Ⅲ 广度优先遍历的算法
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(队列空)
Ⅳ 广度优先搜索算法
我以前做的一个光搜题，给你贴上吧，是一个关于素数变化的题目，输入一对素数，每个是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;
}
Ⅳ 广度优先算法
广度优先算法（Breadth-First Search），同广度优先搜索，又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。
Ⅵ 采用广度优先策略搜索的算法是（ ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
A分支限界法，是利用一种类似评估函数的方法确定己搜索的目标深度，超过后予以剪枝的方法。可以用广度优先搜索实现，按照评估函数值排序进行扩展。
B动态规划法，是利用问题的无后效性进行递推的方式，类似于数列的递推公式，不是搜索算法。
C贪心法，是利用问题本身的特殊性质，在某些方面上具有由简单的最大化原则可以得到直接解的方法，针对某些非多项式的问题可以得到较优解，并作为下一步搜索的基础。
D回溯法，是对问题本身进行深度优先搜索。类似八皇后问题等，本身解空间不大，分支少的时候应该采用。
这样来看，显然是选A的。
Ⅶ 宽度优先搜索算法怎么弄
利用队列来实现。网上代码一堆，你结合自己遇到的编程问题看着仿写即可。
Ⅷ 广度优先搜索是什么
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的
算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的伫列中。一般的实作里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如伫列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
Ⅸ 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是 在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确 定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。 这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。 前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。 启发中的估价是用估价函数表示的，如： f(n) = g(n) + h(n) 其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜 索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。这些就深了，不懂也不影响啦！我们继续看看何谓A*算法。 2、初识A*算法 启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的 策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了 其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点 （除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么 A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空 间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A* 算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n) 这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道 的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别 的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。哈。你懂了吗？肯定没 懂。接着看。 举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。 再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除 的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由 于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这 里就有一个平衡的问题。可难了，这就看你的了！ 好了我的话也说得差不多了，我想你肯定是一头的雾水了，其实这是写给懂A*算法的同志看的。哈哈。你还是找一本人工智能的书仔细看看吧！我这几百字是不足以将A*算法讲清楚的。只是起到抛砖引玉的作用希望大家热情参与吗。
Ⅹ 什么是宽度优先搜索,它的主要特征是
关于宽度优先搜索的具体介绍如下,仅供参考,希望对你有帮助！
1.宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
2.宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止 。
3.另外它也叫广度优先搜索算法,英语：Breadth-First-Search，缩写为BFS，也译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。