2.2 数据结构之 队列与BFS (C语言版）

  

编程总结

在刷题之前需要反复练习的编程技巧，尤其是手写各类数据结构实现，它们好比就是全真教的上乘武功。

本学习来自 leetcode，整理提炼.
https://leetcode-cn.com/leetbook/read/queue-stack/kyozi/

广度优先搜索（BFS）是一种遍历或搜索数据结构（如树或图）的算法。
如前所述，我们可以使用 BFS 在树中执行层序遍历。
我们也可以使用 BFS 遍历图。例如，我们可以使用 BFS 找到从起始结点到目标结点的路径，特别是最短路径。
我们可以在更抽象的情景中使用 BFS 遍历所有可能的状态。在这种情况下，我们可以把状态看作是图中的结点，而以合法的过渡路径作为图中的边。

1. 解释队列和BFS的关系.

广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。
这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。








  1. 结点的处理顺序是什么？
    在第一轮中，我们处理根结点。在第二轮中，我们处理根结点旁边的结点；在第三轮中，我们处理距根结点两步的结点；等等等等。
    与树的层序遍历类似，越是接近根结点的结点将越早地遍历。

如果在第 k 轮中将结点 X 添加到队列中，则根结点与 X 之间的最短路径的长度恰好是 k。也就是说，第一次找到目标结点时，你已经处于最短路径中。

  1. 队列的入队和出队顺序是什么？
    如上面的动画所示，我们首先将根结点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。值得注意的是，新添加的节点不会立即遍历，而是在下一轮中处理。

结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。

广度优先搜索 - 模板

之前，我们已经介绍了使用 BFS 的两个主要方案：遍历或找出最短路径。通常，这发生在树或图中。正如我们在章节描述中提到的，BFS 也可以用于更抽象的场景中。在本文中，我们将为你提供一个模板。然后，我们在本文后提供一些习题供你练习。在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常，结点将是实际结点或是状态，而边缘将是实际边缘或可能的转换。

286. 墙与门


待分析。。。。。on 20210418.

// 反向思维，从门开始找
typedef struct {
	int x;
	int y;
	int step;
} WallsStepStr;

void wallsAndGates(int **rooms, int roomsSize, int *roomsColSize) {
	if ((roomsSize == 0) || (*roomsColSize == 0)) {
		return;
	}
	int row = roomsSize;
	int col = *roomsColSize;
	WallsStepStr *wallStep = (WallsStepStr *)malloc(sizeof(WallsStepStr) * row * col);
	int stepX[] = { 0, 0, -1, 1 };  // Up Down Left Right of X-Axis 
	int stepY[] = { 1, -1, 0, 0 };  // Up Down Left Right of Y-Axis 
	int i, j;
	int head = 0;
	int tail  = 0;   // 甚至都不用考虑队列满的情况 
	// 找门 
	for (i = 0; i < row; i++) {
		for (j = 0; j < col; j++) {
			if (rooms[i][j] == 0) {        // 0 为门
				wallStep[tail].x = i;
				wallStep[tail].y = j;
				wallStep[tail++].step = 0; // 进队列
			}
		}
	}
	// 以门为起点开始BFS 
	while (head != tail) {
		// 先出个门 
		int xx = wallStep[head].x;
		int yy = wallStep[head].y;
		int curStep = wallStep[head++].step; // 出队列
		for (i = 0; i < 4; i++) {
			int xTmp = xx + stepX[i];
			int yTmp = yy + stepY[i];
			if ((xTmp >= 0) && (xTmp < row) && (yTmp >= 0) && (yTmp < col) && (rooms[xTmp][yTmp] == INT_MAX)) {
				rooms[xTmp][yTmp] = curStep + 1;      // 这里如果将rooms[xTmp][yTmp]改为curStep+1后，
													  // 下一次别的门遍历到这个rooms就不会进入这个判断了，所以先到先得，
													  // 先遍历到这个rooms的门就是这个rooms能到达的最近的门
				wallStep[tail].x = xTmp;
				wallStep[tail].y = yTmp;
				wallStep[tail++].step = curStep + 1;  // 将当前出队的元素相邻元素入队 
			}
		}
	}
}
相关文章
C/C++开发最新文章
热门教程