欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广度优先搜索bfs

程序员文章站 2022-06-11 20:37:49
...

  一、含义

广度优先搜索bfs

这张图非常形象,并且将每个节点访问的先后次序表示出来了,广搜即一层一层的向下寻找,因此适用于寻找最短路径问题。可将这张图看做要从 V1去往V8,没有连线的V之间,无法通过一步转移达到,广搜每一步搜索的时候,只选择可以经过一步状态转移就能达到的相邻节点。

二、写程序要用到的

广搜使用queue队列配合结构体来实现。

广度优先搜索bfs

几个方法:

先定义一个节点的结构体:

typedef struct{
	int x;//节点的横纵坐标
	int y;
}NODE;

NODE a;

再定义一个以该结构体类型作为元素的队列Q

queue<NODE> Q;

1、Q.pop();//弹出队列中最前面的一个元素,即最早进入的那个元素,让他消失。

2、Q.front();//取出队列中最前面的一个元素的值。

3、Q.empty();//判断队列是否为空。

4、Q.push(a);//将一个相应类型的元素压入队列中。

三、核心代码(模板)

void bfs(int x,int y,int max) {

	node s,p,b;
	s.x=x;
	s.y=y;
	N.push(s);//将起始元素压入队列
	visit[x][y]=true;//访问过了起始元素,标记一下,以免重复访问
	while(!N.empty()) {
		p = N.front();//取出队列最前面的那个元素,以他为新的支点找相邻的可经一步转移达到的状态
		N.pop();
		for(i=0; i<4; i++) {//原题是有上下左右四个方向可走,所以这里即搜索相邻的四个方向
			b.x=p.x+pos[i][0];//对横纵坐标的变换处理
			b.y=p.y+pos[i][1];
			if(valid(b.x,b.y,max)&&!visit[b.x][b.y]) {//判断是否满足入队条件,即未被访问过,未越界
				N.push(b);
				visit[b.x][b.y]=true;//访问过了节点元素,标记一下
			}

		}
	}



}

贴题:洛谷->试炼场->广度优先搜索

 

相关标签: acm