广度算法
Ⅰ 关于广度优先搜索算法
广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。
这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！
如下是一段迷宫的最佳路径求解算法。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
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;
}
Ⅱ c语言广度优先算法
既然b[i]记录的是前驱城市。
那也就是通过i的前一个城市存在b[i]中，能保证从A到H是最短的。
Ⅲ 广度优先算法和深度优先算法哪个可以求无向图的所有连通分量，具体什么原理
你好，广度优先和深度优先都可以求出无向图的所有连通分量，他们的原理都是遍历，一个是先按广度进行遍历，另外一个是先按深度进行遍历。
Ⅳ 广度优先 算法，各位帮帮。。急
个人对广度优先算法的理解是每次优先遍历父结点下的直接子结点，遍历完这些直接子结点之后再从这些子结点开始遍历他们的直接子结点，以此类推下去，直到找到终点。所以，此处肯定是需要使用到迭代了。在此我想写出我的思路来与楼主交流下。
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的回路。
Ⅳ 广度优先法(BFS)算法
//图定义
typedef int InfoType;
#define INF 65536
#define MAXV 100 //最大顶点个数
//以下定义邻接矩阵类型
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int vexnum,arcnum; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct ANode //弧的结点结构类型
{ int adjvex; //该弧的终点位置
struct ANode *nextarc; //指向下一条弧的指针
InfoType info; //该弧的相关信息,这里用于存放权值
} ArcNode;
typedef int Vertex;
typedef struct Vnode //邻接表头结点的类型
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
int visited[MAXV]; //全局数组
//广度优先搜索
void BFS(ALGraph *G,int v)
{
ArcNode *p;
int queue[MAXV], front=0, rear=0; //定义循环队列并初始化
int visited[MAXV]; //定义存放结点的访问标志的数组
int w, i;
for (i=0; i<G->n; i++)
{
visited[i]=0; //访问标志数组初始化
}
printf("%3d",v); //输出被访问顶点的编号
visited[v]=1; //置已访问标记
rear = (rear+1)%MAXV;
queue[rear] = v; //v进队
while (front != rear) //若队列不空时循环
{
front = (front+1)%MAXV;
w = queue[front]; //出队并赋给w
p = G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
while (p != NULL)
{
if (visited[p->adjvex] == 0) //若当前邻接顶点未被访问
{
printf("%3d", p->adjvex); //访问相邻顶点
visited[p->adjvex] = 1; //置该顶点已被访问的标志
rear = (rear+1)%MAXV; //该顶点进队
queue[rear] = p->adjvex;
}
p = p->nextarc; //找下一个邻接顶点
}
}
printf("\n");
}
Ⅵ 怎样理解深度优先算法和广度优先算法
胡说八道.... 深度优先:前序遍历 广度优先:按层遍历
Ⅶ 广度优先算法的特性
空间复杂度 因为所有节点都必须被储存，因此BFS的空间复杂度为 O(|V| + |E|)，其中 |V| 是节点的数目，而 |E| 是图中边的数目。注：另一种说法称BFS的空间复杂度为O(B)，其中 B 是最大分支系数，而 M 是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。 若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，BFS仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS的改良算法成本一致搜寻法（en:uniform-cost search）来解决。然而，若非加权图形，则所有边的长度相等，BFS就能找到最近的最佳解。
Ⅷ 广度优先算法的简介
由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。
Ⅸ 广度优先算法（宽搜）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属性，可保万无一失
希望对你有帮助~
Ⅹ 广度优先法(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'); }