广度优先 算法，各位帮帮。。急
以搜索为例，下面两种介绍了深搜与广搜的具体实现。
算法博大精深，望楼主好好学习啊
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
算法分析：
每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深搜相同。
它没有固定的写法， 但是大框都差不多， 一定要使用队列， 因为队列的存在可以维护程序按照广度优先的方式进行搜索。即层次遍历
可以给你一份我作过的一个题的代码，大体上就是这个样子
/****************************************************\
*
* Title: Rescue
* From: HDU 1242
* AC Time: 2012.01.12
* Type: 广度优先搜索求最短步数
* Method :从目标结点向回搜索，初始结点有多个
*
\****************************************************/
#include
#include
#define DATASIZE 201
#define QUEUESIZE 65536
typedef struct
{
int x,y;
}CPOINT;
int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa);
int direction[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main(void)
{
int m,n,i,j,res;
CPOINT cpa;
char map[DATASIZE][DATASIZE];
freopen("c:\\in.data","r",stdin);
while(scanf("%d%d%*c",&n,&m) != EOF) {
for(i = 0 ; i < n ; i++) {
gets(map[i]);
for(j = 0 ; j < m ; j++) {
if(map[i][j] == 'a') {
cpa.x = i;
cpa.y = j;
}
}
}
res = bfs(map, n, m, cpa);
if(res) {
printf("%d
",res);
} else {
printf("Poor ANGEL has to stay in the prison all his life.
");
}
}
return 0;
}
int bfs(char map[][DATASIZE], int n, int m, CPOINT cpa)
{
CPOINT q[QUEUESIZE],u,np;
int vis[DATASIZE][DATASIZE],step[DATASIZE][DATASIZE],i,front,rear,res;
memset(q, 0, sizeof(q));
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
front = rear = res = 0;
q[rear++] = cpa;
vis[cpa.x][cpa.y] = 1;
step[cpa.x][cpa.y] = 0;
while(front <= rear) {
u = q[front++];
if(map[u.x][u.y] == 'r') {
res = step[u.x][u.y];
break;
}
for(i = 0 ; i < 4; i++) {
np.x = u.x + direction[i][0];
np.y = u.y + direction[i][1];
if(np.x >= 0 && np.x = 0 && np.y < m && !vis[np.x][np.y] && map[np.x][np.y] != '#' ) {
vis[np.x][np.y] = 1;
q[rear++] = np;
step[np.x][np.y] = step[u.x][u.y] + 1;
if(map[np.x][np.y] == 'x') {
++step[np.x][np.y];
}
}
}
}
return res;
}
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的回路。
如过我用C语言来写，你能看懂么？
如过我用C语言来写，你能看懂么？
1、程序开始(设置参数和数据结构)
2、获得起始点，建立数据头，建立行走历史
3、根据当前节点，对所有可能的下一步行走方法进行（4）步所述内容，CASE完毕删除当前节点（包括行走的历史和当前位置）。
4、判断行走的可行性。如果可行，判断是否达到目标，如果达到目标，输出行走历史并结束程序；如果没有达到目标，记录当前的行走历史和当前的位置重复第（3）步内容；如果判断当前步不可行，不做任何操作，转入第（3）步内容。
5、如果达到一定的深度没有答案，结束程序，提示没有结果。
数据结构采用这样的形式：一个链表头指向了当前深度下的所有可行的结果，然后遍历这个链表，对每种结果的下一步进行判断，如果可行就创建新的链表来记录。记得：同一深度的结果必须在同一个链表中。
我的程序中是只用了一个链表来存储这些结果的，一个头节点永远指向结果的头，一个当前节点指向正在计算下一步的那个节点，（当前节点之前的结果比当前的节点和当前节点之后的结果的深度要深一层，即我把新的可行的结果的数据存储到链表的头上去，当前节点的所有可能的下一步的情况都考虑了之后就删除当前节点）当当前节点指向都节点的时候，链表内的所有结果的深度是一样的。
不知道你明白不明白。我就是用这种思路用VC的MFC编辑了一个求解类似“农夫过河”问题的广度优先A*搜索算法的程序。
如果要算法流程图可以再找我……
呵呵...俺数学不好.帮不了你..呵呵
好复杂啊~
我写过类似的算法，你可以去下载了看看
http://download.csdn.net/source/257602
这个用A*算法或者Djsktra比较好
不懂，楼主这个游戏做出来后可否让俺先体验下?
宁肾美卡： 广度优先就是一层一层的往下访问,该层从左到右访问结束之后再访问下一层,这里以二叉树为例,用数组存放该二叉树,根节点位置定为1(零号位置不用,你也可以用,这不规定,我这里不用而已)结构如下:12 34 5 6 78 9 10 11 12 13 14 ...
漳平市18389099730： 广度优先搜索C语言算法 - ？
宁肾美卡： 它没有固定的写法, 但是大框都差不多, 一定要使用队列, 因为队列的存在可以维护程序按照广度优先的方式进行搜索.即层次遍历 可以给你一份我作过的一个题的代码,大体上就是这个样子/****************************************************\ * * ...
漳平市18389099730： 关于广度优先搜索算法 - ？
宁肾美卡： 广度优先搜索算法,是按层遍历各个结点,以求出最短或最优的解,常用于计算路径的最短距离,和最佳通路.例如:迷宫的最短路径计算,推箱子的移动最小步数等小游戏,都是按广度搜索来进行的.这个算法是教程中很经典的,有很多例子...
漳平市18389099730： 什么是宽度优先搜索 - ？
宁肾美卡： 1. 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型.Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想.其别名又叫BFS,属于一种盲目搜寻...
漳平市18389099730： 急!!C++深度优先算法和广度优先算法 - ？
宁肾美卡： 以搜索为例,下面两种介绍了深搜与广搜的具体实现. 算法博大精深,望楼主好好学习啊 1. 深度搜索 void Graph::DFS(const int v, int visited[]) { cout<visited[v] = 1; //顶点 v 作访问标记 int w = GetFirstNeighbor(v););//取 v 的第一个邻...
漳平市18389099730： 广度优先算法(宽搜)pascal - ？
宁肾美卡： 下面是一段delphi代码:算法核心代码,为增强算法通用性,将窗体的一个treeview和ADOQuery引用到局部变量中,作为对象引用,不创建,也不释放,相当于别名 procedure Tfrm.FmtTree(); var i,j :integer; leafList,leafListPlus: TList; leaf,...
漳平市18389099730： 深度优先搜索遍历和广度优先搜索的遍历序列及具体步骤和原因, - ？
宁肾美卡： 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,以此...
漳平市18389099730： 深度优先搜索法和广度优先搜索法 - ？
宁肾美卡： 深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图.在深度优先搜索中,对于最新发现的结点,如果它还有以此为起点而未搜过的边,就沿着边继续搜索下去.当结点v的所有边都已被探寻过,搜索将回溯到发现结点v有那条边的始结点....
漳平市18389099730： 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系? - ？
宁肾美卡： 1、何谓启发式搜索算法 在说它之前先提提状态空间搜索.状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程.通俗点说,就是 在解一个问题时,找到一条解题的过程可以从求解的开始到...
漳平市18389099730： 广度优先搜索怎么保证最优解啊?(新手不懂,求指导) - ？
宁肾美卡： 广度优先搜索法的显著特点是: (1)在产生新的子结点时,深度越小的结点越先得到扩展,即先产生它的子结点.为使算法便于实现,存放结点的数据库一般用队列的结构. (2)无论问题性质如何不同,利用广度优先搜索法解题的基本算法是相...
