广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) - 层层递进

小鱼儿 2023-02-10 12:28 21阅读 0赞

#  广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) - 层层递进 #

深度优先搜索方法可用于解决从迷宫起点开始寻找一条通往迷宫中目标位置最短路径的问题。广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) 也可以解决这个问题。

使用二维数组来存储这个迷宫。最开始的时候在迷宫 `(1, 1)` 处，可以往右走或者往下走。深度优先搜索的方法是先往右边走，然后一直尝试下去，直到走不通的时候再回到这里。深度优先可以通过函数的递归实现。广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) 方法通过一层一层扩展的方法来寻找目标位置。扩展时每发现一个点就将这个点加入到队列中，直至走到目标位置 `(ph, qw)` 时为止。

最开始在入口 `(1, 1)` 处，一步之内可以到达的点有 `(1, 2)` 和 `(2, 1)`。  
![在这里插入图片描述][20200520235526214.png_pic_center]

但是目标位置并不在这两个点上，只能通过 `(1, 2)` 和 `(2, 1)` 这两点继续往下走。比如现在走到了 `(1, 2)` 这个点，之后又能够到达 `(2, 2)`。再看看通过 `(2, 1)` 又可以到达 `(2, 2)` 和 `(3, 1)`。此时会发现 `(2, 2)` 这个点既可以从 `(1, 2)` 到达，也可以从 `(2, 1)` 到达，并且都只使用了 2 步。为了防止一个点多次被走到，这里需要一个数组来记录一个点是否已经被走到过。  
![在这里插入图片描述][20200520235729837.png_pic_center]

此时 2 步可以走到的点就全部走到了，有 `(2, 2)` 和 `(3, 1)`，可是目标位置并不在这两个点上。看来没有别的办法，还得继续往下尝试，看看通过 `(2, 2)` 和 `(3, 1)` 这两个点还能到达哪些新的没有走到过的点。通过 `(2, 2)` 这个点我们可以到达 `(2, 3)` 和 `(3, 2)`，通过 `(3, 1)` 可以到达 `(3, 2)` 和 `(4, 1)`。现在 3 步可以到达的点有 `(2, 3)`、`(3, 2)` 和 `(4, 1)`，依旧没有到达目标的所在点，所以我们需要继续重复刚才的做法，直到找到目标位置所在点为止。  
![在这里插入图片描述][20200520235947592.png_pic_center]

回顾一下刚才的算法，可以用一个队列来模拟这个过程。在这里我们用一个结构体数组来实现队列。

struct note {
    	int xw; // 横坐标
    	int yh; // 纵坐标
    	int step; // 步数 
    };
    
    struct note que[2500]; // 因为地图大小不超过 50*50，因此队列扩展不会超过 2500
    int head, tail;
    int map[51][51] = { 0 }; // 用来存储地图 
    int book[51][51] = { 0 }; // 数组 book 的作用是记录哪些点已经在队列中了，防止点被重复扩展，并全部初始化为 0
    
    /* 最开始的时候需要进行队列初始化，即将队列设置为空 */
    head = 0;
    tail = 0;
    
    // 第一步将 (1, 1) 加入队列，并标记 (1, 1) 已经走过。
    que[tail].xw = 1;
    que[tail].yh = 1;
    que[tail].step = 0;
    tail++;
    
    book[1][1] = 1;

![在这里插入图片描述][2020052100021737.png_pic_center]

然后从 `(1, 1)` 开始，先尝试往右走到达了 `(1, 2)`。

txw = que[head].xw + 1;
    tyh = que[head].yh;

需要判断 `(1, 2)` 是否越界。

if ((txw < 1) || (txw > W) || (tyh < 1) || (tyh > H))
    {
    	continue;
    }

再判断 `(1, 2)` 是否为障碍物或者已经在路径中。

if ((0 == map[tyh][txw]) && (0 == book[tx][ty]))
    {
    }

如果满足上面的条件，则将 `(1, 2)` 入队，并标记该点已经走过。

book[tyh][txw] = 1; // bfs 每个点通常情况下只入队一次，同深搜不同，不需要将 book 数组还原
    // 插入新的点到队列中
    que[tail].xw = txw;
    que[tail].yh = tyh;
    que[tail].step = que[head].step + 1; // 步数是父亲的步数 + 1
    tail++;

![在这里插入图片描述][2020052100263473.png_pic_center]

接下来还要继续尝试往其他方向走。在这里我们规定一个顺序，即按照顺时针的方向来尝试 `(右 -> 下 -> 左 -> 上)`。我们发现从 `(1, 1)` 还是可以到达 `(2, 1)`，因此也需要将 `(2, 1)` 也加入队列，代码实现与刚才对 `(1, 2)` 的操作是一样的。  
![在这里插入图片描述][2020052100291518.png_pic_center]

对 `(1, 1)` 扩展完毕后，此时我们将 `(1, 1)` 出队 (因为扩展完毕，已经没用了)。

head++;

接下来我们需要在刚才新扩展出的 `(1, 2)` 和 `(2, 1)` 这两个点上继续向下探索 (因为还没有到达目标所在的位置，所以还需要继续)。`(1, 1)` 出队之后，现在队列的 `head` 正好指向了 `(1, 2)` 这个点，现在我们需要通过这个点继续扩展，通过 `(1, 2)` 可以到达 `(2, 2)`，并将 `(2, 2)` 也加入队列。  
![在这里插入图片描述][20200521003544352.png_pic_center]

`(1, 2)` 这个点已经处理完毕，于是可以将 `(1, 2)` 出队。`(1, 2)` 出队之后，`head` 指向了 `(2, 1)` 这个点。通过 `(2, 1)` 可以到达 `(2, 2)` 和 `(3, 1)`，但是因为 `(2, 2)` 已经在队列中，因此我们只需要将 `(3, 1)` 入队。  
![在这里插入图片描述][20200521003645468.png_pic_center]

到目前为止我们已经扩展出从起点出发 2 步以内可以到达的所有点，可是依旧没有到达目标所在的位置，因此还需要继续扩展，直到找到目标所在的点才算结束。

为了方便向四个方向扩展，这里需要一个 `next` 数组：

// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };

## 1. D:\\visual\_studio\_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt ##

`input.txt` 第一行是测试用例个数 2，后续依次为具体测试用例数据。  
测试用例第一行有两个数 `YH` 和 `XW`，`YH = 5` 表示迷宫的行数，`XW = 4` 表示迷宫的列数。  
紧接着一行表示起始点坐标 `(start_yh, start_xw)` 和目标位置坐标 `(end_yh, end_xw)`，注意起始点为 `(0, 0)`。  
接下来 `YH = 5` 行 `XW = 4` 列为迷宫地图，`0` 表示空地，`1` 表示障碍物。

2
    5 4
    0 0 3 2
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1
    5 4
    0 0 3 2
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## 2. yongqiang.cpp ##

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int end_yh = 0, end_xw = 0;
    
    int inference(int map_data[50][50], int start_yh, int start_xw, int YH, int XW)
    {
    	int ret = 0;
    	// 数组 book 记录哪些点已经在队列中了，防止点被重复扩展，并全部初始化为 0
    	int book[50][50] = { 0 };
    	// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
    	// 地图大小不超过 50*50，因此队列扩展不会超过 2500
    	int queue_data[2500][2] = { 0 };
    	int head = 0, tail = 0;
    	int dist_matrix[50][50] = { 0 };
    	int flag = 0;
    	int min_step = 0;
    
    	// 从起点开始搜索
    	queue_data[tail][0] = start_yh;
    	queue_data[tail][1] = start_xw;
    	tail++;
    	book[start_yh][start_xw] = 1;
    	dist_matrix[start_yh][start_xw] = 0;
    
    	flag = 0; // 用来标记是否到达目标点，0 表示暂时没有到达，1 表示已经到达
    	while (head < tail)
    	{
    		int poph = 0, popw = 0, step = 0;
    
    		poph = queue_data[head][0];
    		popw = queue_data[head][1];
    		head++;
    		step = dist_matrix[poph][popw];
    
    		// 枚举四个方向
    		for (int k = 0; k < 4; k++)
    		{
    			int tyh = 0, txw = 0;
    
    			// 计算下一个点的坐标 
    			tyh = poph + next[k][0];
    			txw = popw + next[k][1];
    
    			// 判断是否越界
    			if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW))  // 判断是否越界 
    			{
    				continue;
    			}
    
    			// 0 表示空地，1 表示障碍物
    			if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    			{
    				// 标记这个点已经走过
    				book[tyh][txw] = 1;
    				// 插入新的点到队列中
    				queue_data[tail][0] = tyh;
    				queue_data[tail][1] = txw;
    				tail++;
    				// 这个点的步数是父亲节点的步数 + 1
    				dist_matrix[tyh][txw] = step + 1;
    			}
    
    			if ((tyh == end_yh) && (txw == end_xw)) {
    				min_step = step + 1;
    				flag = 1;
    				break;
    			}
    		}
    
    		if (1 == flag) {
    			break;
    		}
    	}
    
    	ret = min_step;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num = 0;
    	cin >> case_num;
    	cout << case_num << endl;
    
    	for (int idx = 1; idx <= case_num; idx++)
    	{
    		int start_yh = 0, start_xw = 0;
    		int YH = 0, XW = 0;
    		int ret = 0;
    		// (height, weight)
    		int map_data[50][50] = { 0 }; // 存储地图
    
    		cin >> YH >> XW; // initialization
    		cin >> start_yh >> start_xw >> end_yh >> end_xw; // initialization
    
    		cout << YH << XW << endl;
    		cout << start_yh << start_xw << end_yh << end_xw << endl;
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cin >> map_data[h][w];
    			}
    		}
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cout << map_data[h][w];
    			}
    			cout << endl;
    		}
    
    		ret = inference(map_data, start_yh, start_xw, YH, XW);
    
    		cout << "CASE #" << idx << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int end_yh = 0, end_xw = 0;
    
    int inference(int map_data[50][50], int start_yh, int start_xw, int YH, int XW)
    {
    	int ret = 0;
    	// 数组 book 记录哪些点已经在队列中了，防止点被重复扩展，并全部初始化为 0
    	int book[50][50] = { 0 };
    	// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
    	// 地图大小不超过 50*50，因此队列扩展不会超过 2500
    	int queue_data[2500][2] = { 0 };
    	int head = 0, tail = 0;
    	int dist_matrix[50][50] = { 0 };
    	int flag = 0;
    	int min_step = 0;
    
    	// 从起点开始搜索
    	queue_data[tail][0] = start_yh;
    	queue_data[tail][1] = start_xw;
    	tail++;
    	book[start_yh][start_xw] = 1;
    	dist_matrix[start_yh][start_xw] = 0;
    
    	flag = 0; // 用来标记是否到达目标点，0 表示暂时没有到达，1 表示已经到达
    	while (head < tail)
    	{
    		int poph = 0, popw = 0, step = 0;
    
    		poph = queue_data[head][0];
    		popw = queue_data[head][1];
    		head++;
    		step = dist_matrix[poph][popw];
    
    		// 枚举四个方向
    		for (int k = 0; k < 4; k++)
    		{
    			int tyh = 0, txw = 0;
    
    			// 计算下一个点的坐标 
    			tyh = poph + next[k][0];
    			txw = popw + next[k][1];
    
    			// 判断是否越界
    			if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW))  // 判断是否越界 
    			{
    				continue;
    			}
    
    			// 0 表示空地，1 表示障碍物
    			if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    			{
    				// 标记这个点已经走过
    				book[tyh][txw] = 1;
    				// 插入新的点到队列中
    				queue_data[tail][0] = tyh;
    				queue_data[tail][1] = txw;
    				tail++;
    				// 这个点的步数是父亲节点的步数 + 1
    				dist_matrix[tyh][txw] = step + 1;
    			}
    
    			if ((tyh == end_yh) && (txw == end_xw)) {
    				min_step = step + 1;
    				flag = 1;
    				break;
    			}
    		}
    
    		if (1 == flag) {
    			break;
    		}
    	}
    
    	ret = min_step;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num = 0;
    	cin >> case_num;
    	cout << case_num << endl;
    
    	for (int idx = 1; idx <= case_num; idx++)
    	{
    		int start_yh = 0, start_xw = 0;
    		int YH = 0, XW = 0;
    		int ret = 0;
    		// (height, weight)
    		int map_data[50][50] = { 0 }; // 存储地图
    
    		cin >> YH >> XW; // initialization
    		cin >> start_yh >> start_xw >> end_yh >> end_xw; // initialization
    
    		cout << YH << XW << endl;
    		cout << start_yh << start_xw << end_yh << end_xw << endl;
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cin >> map_data[h][w];
    			}
    		}
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cout << map_data[h][w];
    			}
    			cout << endl;
    		}
    
    		ret = inference(map_data, start_yh, start_xw, YH, XW);
    
    		cout << "CASE #" << idx << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

### 2.1 `D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\output.txt` ###

Start of the program, start = 54
    Start of the program, start = 54
    
    2
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #1 = 7
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #2 = 7
    
    End of the program, end = 56
    End of the program, end = 56
    Total time taken by CPU: 0.002000
    Exiting of the program...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

1959 年，Edward F. Moore 率先在“如何从迷宫中寻找出路“这一问题中提出了广度优先搜索算法。1961 年，C. Y. Lee 在”电路板布线“这一问题中也独立提出了相同的算法。

## 3. 广度优先搜索 / 宽度优先搜索 (Breadth First Search，BFS) ##

宽度优先搜索就像是一次病毒的扩散，目的是要以最快的速度扩散到最广的范围。

深度搜索认准一条路非给你走到底不可。  
广度搜索慢慢地一步步地试探能不能符合要求。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

## References ##

《啊哈！算法》 - 啊哈磊

[20200520235526214.png_pic_center]: https://img-blog.csdnimg.cn/20200520235526214.png#pic_center
[20200520235729837.png_pic_center]: https://img-blog.csdnimg.cn/20200520235729837.png#pic_center
[20200520235947592.png_pic_center]: https://img-blog.csdnimg.cn/20200520235947592.png#pic_center
[2020052100021737.png_pic_center]: https://img-blog.csdnimg.cn/2020052100021737.png#pic_center
[2020052100263473.png_pic_center]: https://img-blog.csdnimg.cn/2020052100263473.png#pic_center
[2020052100291518.png_pic_center]: https://img-blog.csdnimg.cn/2020052100291518.png#pic_center
[20200521003544352.png_pic_center]: https://img-blog.csdnimg.cn/20200521003544352.png#pic_center
[20200521003645468.png_pic_center]: https://img-blog.csdnimg.cn/20200521003645468.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200519223640369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200521005249902.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200521005438928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200521005538775.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200520220442784.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center