devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

BFS基础讲解（广度优先搜索）_bfs 讲解

作者：正经夜光杯 | 2024-06-19 18:02:45

赞

踩

bfs 讲解

BFS

BFS基础

BFS是什么？

BFS 是 Breadth First Search 的缩写，即广度优先搜索（也称宽度优先搜索）。
BFS 是搜索的手段之一。

BFS的作用是什么？

(1)：求最短路径、最少操作
(2)：求联通块（与 DFS 类似）

BFS的结构

BFS 的搜索路线是以一层一层、由近及远的顺序进行搜索的。
以一张图为例：

起始点为 a，终点为 f
求最少经过几个点能从点 a 到达点 f
第一层为起点，即点 a
第二层为点 a 能去到的位置，即点 b、c、d
第三层为点 b、c、d 能去到的位置，即点 e、f
此刻在第三层已经到达了点 f，即到达了终点。
那么我们便可以得出最少经过的点数了，即为 3 个点（a、d、f）

用圈层图来表示：从起点所在的第一层开始，搜到终点第一次出现对应的那层，然后结束，即为最外层。

用树状图来表示：从起点一直搜到终点

代码实现

在 BFS 中，我们需要用到一个队列，来实现一层一层访问节点的顺序。

代码框架

0、头文件
#include <stdio.h>
#include <string.h>
#include <queue>

  • 1
  • 2
  • 3
1、准备结构体
// 开一个结构体
struct node {
	int x, y;  // 节点所在位置
	int step;  // 节点所在层数
}st, ed;  // 起点和终点

  • 1
  • 2
  • 3
  • 4
  • 5
2、编写 BFS 函数

以二维BFS为例

const int maxn = ...;
int gx, gy;  // 终点的位置，在 main 里读入
int n, m;    // 图的边界，在 main 里读入
bool vis[maxn][maxn];  // 记录位置是否被走过
int map[maxn][maxn];   // 建一个二维数组来存放图的内容
// 以四个方向为例：上下左右
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int bfs(int x, int y)
{
	queue<node>q;  // 开一个队列
	// 对起点初始化
	st.x = x;
	st.y = y;
	st.step = 0;  // 初始层次为 0
	memset(vis, false, sizeof(vis));
	vis[x][y] = true;  // 标记初始位置已被走过
	q.push(st);   // 先将起点放入队列
	
	while(!q.empty())  // 直到队列为空 或 找到终点后，终止循环
	{
		st = q.front();  // 将起点更新为队列中的第一个结构
		q.pop();  // 然后将队列中第一个结构删除
		
		// 找到终点，就结束函数，并返回此时层数
		if(st.x==gx && st.y==gy)
			return st.step;
		
		for(int i=0; i<4; i++)
		{
			ed.x = st.x + dx[i];
			ed.y = st.y + dy[i];
			ed.step = st.step + 1;  //层数加一
			
			// 若该位置已走过，则进入下一循环，避免重复
			// 若超出边界，则进入下一循环
			// 其中 n、m 为边界
			if(vis[ed.x][ed.y] || map[ed.x][ed.y]=='题目条件' || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m)
				continue;
			
			vis[ed.x][ed.y] = true; //标记该位置已走过
			
			// 若还未到终点，则将其放入队列，变成下次调用的起点
			q.push(ed);
		}
	}
	return -1;  // 若找不到终点，则按题目要求返回特定值
}	

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
3、编写 main 函数
int main()
{
	int sx, sy;   //起点
	scanf("%d %d", &n, &m);    //读入边界
	scanf("%d %d", &sx, &sy);  //读入起点
	scanf("%d %d", &gx, &gy);  //读入终点
	
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			scanf("%c", &map[i][j]);
	
	if(sx==gx && sy==gy)
		printf("0\n");
	else
		printf("%d\n", bfs(sx, sy));
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

例题

BFS经典例题合集（转）

一维BFS

主要目的是熟悉BFS代码

HDU-1548
#include <stdio.h>
#include <string.h>
#include <queue>

struct node {
    int x;
    int step;
} st, ed;

int gx;
int n;
int a[205];
bool vis[205];

int bfs(int x)
{
    std::queue<node>q;
    st.x = x;
    st.step = 0;
    memset(vis, false, sizeof(vis));
    vis[x] = true;
    q.push(st);
    
    while(!q.empty())
    {
        st = q.front();
        q.pop();
        
        if(st.x==gx)
    		return st.step;
    		
        for(int i=-1; i<=1; i+=2)
        {
            ed.x = st.x + i * a[st.x];
            ed.step = st.step + 1;
            
            if(ed.x<=0 || ed.x>n || vis[ed.x])
                continue;
            
            vis[ed.x] = true;
            q.push(ed);
        }
    }
    return -1;
}

int main()
{
    int sx;
    while(scanf("%d", &n)!= EOF && n)
    {
        scanf("%d %d", &sx, &gx);
        
        for(int i=1; i<=n; i++)
            scanf("%d", &a[i]);
        
        if(sx==gx) printf("0\n");
        else printf("%d\n", bfs(sx));
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
HDU-2717
#include <stdio.h>
#include <string.h>
#include <queue>

struct node {
	int x;
	int step;
} st, ed;

const int maxn = 100005;
int gx;
bool vis[maxn];

int bfs(int x)
{
	std::queue<node>q;
	st.x = x;
	st.step = 0;
	memset(vis, false, sizeof(vis));
	vis[x] = true;
	q.push(st);
	
	while(!q.empty())
	{
		st = q.front();
		q.pop();
		
		if(st.x == gx)
			return st.step;
		
		for(int i=0; i<3; i++)
		{
			if(i==0)
				ed.x = st.x + 1;
			else if(i==1)
				ed.x = st.x - 1;
			else if(i==2)
				ed.x = st.x * 2;
			ed.step = st.step + 1;
			
			if(ed.x<0 || ed.x>maxn || vis[ed.x])
				continue;
			
			vis[ed.x] = true;
			q.push(ed);
		}
	}
	return 0;
}

int main()
{
	int sx;
	while(scanf("%d %d", &sx, &gx) != EOF)
	{
		if(sx >= gx)
		{
			printf("%d\n", sx - gx);
			continue;
		}
		printf("%d\n", bfs(sx));
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

二维BFS

大多数题目都是二维BFS，所以之前所写的代码框架也是按二维BFS来写的

HDU-1372
#include <stdio.h>
#include <queue>

struct node{
	int x, y;
	int step;
} st, ed;

int gx, gy;
int dx[8] = {-2,-2,2,2,-1,-1,1,1};
int dy[8] = {-1,1,-1,1,-2,2,-2,2};

int bfs(int x, int y)
{
	std::queue<node>q;
	st.step = 0;
	st.x = x;
	st.y = y;
	q.push(st);
	while(!q.empty())
	{
		st = q.front();
		q.pop();
		
		if(st.x==gx && st.y==gy)
			return st.step;
		
		for(int i=0; i<8; i++)
		{
			ed.x = st.x + dx[i];
			ed.y = st.y + dy[i];
			ed.step = st.step + 1;
			
			if(ed.x<=0 || ed.x>8 || ed.y<=0 || ed.y>8)  continue;
			
			q.push(ed);
		}
	}
	return -1;
}

int main()
{
	int sx, sy;
	char c1, c2;
	while(scanf("%c%d %c%d", &c1, &sy, &c2, &gy) != EOF)
	{
		getchar();
		sx = c1 - 'a' + 1;
		gx = c2 - 'a' + 1;
		if(sx==gx && sy==gy)
			printf("To get from %c%d to %c%d takes 0 knight moves.\n", c1, sy, c2, gy);
		else
			printf("To get from %c%d to %c%d takes %d knight moves.\n",c1, sy, c2, gy, bfs(sx, sy)); 
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
HDU-1728

这题比较特殊！！
如果一路不拐弯，那么 step 是不用增加的。
也就是说，只有拐弯后 step 才会整体都加一，所以这题要在一条直线中的每个点处都判断一次是否到达了终点，因此要在 for 里面（同一个方向）进行判断

#include <stdio.h>
#include <string.h>
#include <queue>

struct node {
    int x, y;
    int step;
} st, ed;

const int maxn = 105;
int gx, gy;
int n, m;
int k;
bool vis[maxn][maxn];
char map[maxn][maxn];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int bfs(int x, int y)
{
    std::queue<node>q;
    st.x = x;
    st.y = y;
    st.step = -1;   // 这题从 -1 开始，因走第一步时相当于拐了一个弯
    memset(vis, false, sizeof(vis));
    vis[x][y] = true;
    q.push(st);
    
    while(!q.empty())
    {
        st = q.front();
        q.pop();
        
        for(int i=0; i<4; i++)
        {
            ed.x = st.x + dx[i];
            ed.y = st.y + dy[i];

			// 一路直走不拐弯
            while(map[ed.x][ed.y] == '.' && ed.x>=1 && ed.x<=m && ed.y>=1 && ed.y<=n)
            {
            	// 这题中 vis 是用来判断是否 q.push
                if(!vis[ed.x][ed.y])
                {
                    vis[ed.x][ed.y] = true;
                    ed.step = st.step + 1;
                    if(ed.x==gx && ed.y==gy && ed.step<=k)
                    	return true;
                    q.push(ed);
                }
                ed.x += dx[i];
                ed.y += dy[i];
            }
        }
    }
    return false;
}
int main()
{
	int T;
    scanf("%d",&T);
    int sx, sy;
    while(T--)
    {
        scanf("%d %d", &m, &n);
        getchar();
        for(int i=1; i<=m; i++)
            scanf("%s", map[i]+1);
        scanf("%d %d %d %d %d", &k, &sy, &sx, &gy, &gx);
        
        if(sx==gx && sy==gy)
        {
            printf("yes\n");
            continue;
        }
        if(bfs(sx, sy))
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82

三维BFS

HDU-2102

这题一定要先输入再处理！！！
这题一定要先输入再处理！！！
这题一定要先输入再处理！！！

不然就会像我一样失去两天的美好时光

这题的重点是处理传送门 ‘#’
围绕这一个问题会展开多个问题

1、若 ‘#’ 的那边是 ‘*’，则会撞死。
处理方法：将 ‘#’ 也改为 ‘*’

2、若 ‘#’ 的那边是也是 ‘#’，则会陷入死循环。
处理方法：将两个 ‘#’ 都改为 ‘*’

#include <stdio.h>
#include <string.h>
#include <queue>

struct node {
	int x, y, z;
	int step;
} st, ed;

const int maxn = 12;
int gx, gy, gz;
int n, m, t;
char map[2][maxn][maxn];
bool vis[2][maxn][maxn];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

bool bfs(int x, int y, int z)
{
	std::queue<node>q;
	st.x = x;
	st.y = y;
	st.z = z;
	st.step = 0;
	memset(vis, false, sizeof(vis));
	vis[z][x][y] = true;
	q.push(st);
	while(!q.empty())
	{
		st = q.front();
		q.pop();
		
		if(st.x==gx && st.y==gy && st.z==gz && st.step<=t)
			return true;
		
		for(int i=0; i<4; i++)
		{
			ed.x = st.x + dx[i];
			ed.y = st.y + dy[i];
			ed.z = st.z;
			ed.step = st.step + 1;
			
			if(map[ed.z][ed.x][ed.y]=='*' || vis[ed.z][ed.x][ed.y] || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m)
				continue;
			
			vis[ed.z][ed.x][ed.y] = true;
			
			if(map[ed.z][ed.x][ed.y]=='#')
				ed.z = (ed.z + 1) % 2;
			q.push(ed);
		}
	}
	return false;
}

int main()
{
	int T;
	scanf("%d", &T);
	int sx, sy, sz;
	while(T--)
	{
		scanf("%d %d %d", &n, &m, &t);
		for(int i=0; i<2; i++)
            for(int j=0; j<n; j++)
                scanf("%s", map[i][j]);
                
        for(int i=0; i<2; i++)
        {
        	for(int j=0; j<n; j++)
            {
            	for(int k=0; k<m; k++)
                {
                    if(map[i][j][k] == 'S')
                    {
                    	sx = j, sy = k, sz = i;
					}
                    else if(map[i][j][k]=='P')
                    {
                    	gx = j, gy = k, gz = i;
					}
                    else if(map[i][j][k] == '#' && map[(i+1)%2][j][k] == '#')
                    {
                        map[i][j][k] = '*';
                        map[(i+1)%2][j][k] = '*';
                    }
                    else if(map[i][j][k] == '#' && map[(i+1)%2][j][k] == '*')
                    {
                    	map[i][j][k] = '*';
					}
                }
			}
		}
		
		if(sx==gx && sy==gy && sz==gz)
		{
			printf("YES\n");
			continue;
		}
		if(bfs(sx, sy, sz))
			printf("YES\n");
		else
			printf("NO\n"); 
	}
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/737292?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号