登录以参加训练计划

1，广度优先搜索概念

广度优先搜索（BFS）是一种经典的算法，用于遍历或搜索树或图中的节点。其核心思想是从一个起始节点出发，首先访问所有的邻接节点，然后再依次访问这些邻接节点的邻接节点，形成一个层次结构的遍历方式。BFS 通常使用队列（Queue）数据结构来跟踪待访问的节点，确保按照层次顺序处理节点。

2，算法特点

广度优先搜索具有以下几个显著的特点：

• 层次遍历：BFS 会从起始节点开始，逐层访问每一层的所有节点，直到所有节点都被访问为止。这使得 BFS 特别适合寻找最短路径问题。（因为最先被找到的节点一定是通过路径最短的。）
• 使用队列：BFS 使用队列来保持待访问的节点，确保先访问的节点先被处理，这也是 BFS 的核心机制。
• 访问标记：为了防止重复访问同一节点，BFS 通常会使用一个布尔数组或集合来标记已访问的节点。

3，适用场景

广度优先搜索适合解决许多问题，包括但不限于：

• 最短路径问题：在无权图中，BFS 可用于寻找从起始节点到目标节点的最短路径。
• 连通性问题：用于检查图的连通性，例如判断一个图是否是连通的。
• 层次关系：BFS 可以用于构建或分析数据的层次结构，如树的层次遍历。
• 寻路问题：在迷宫或地图中找到从起点到终点的路径。

4，数据结构

在实现 BFS 时，通常需要以下几个数据结构：

• 队列：用于跟踪待访问的节点，FIFO（先进先出）原则确保节点按照层次顺序被访问。
• 访问标记：布尔数组或集合用于标记已访问的节点，避免重复访问。

5，时间复杂度

广度优先搜索的时间复杂度通常为 O(V + E)，其中 V 是图中的顶点数量，E 是边的数量。这个复杂度反映了算法需要访问每个节点和每条边。

6，空间复杂度

BFS 的空间复杂度主要由队列和访问标记结构决定：

• 队列的大小在最坏情况下可能达到 O(V)，因为需要存储所有未访问的节点。
• 访问标记的空间复杂度也是 O(V)，用于存储每个节点的访问状态。

7，优缺点

优点

• 找到最短路径：在无权图中，BFS 能够找到从起始节点到任何节点的最短路径。
• 简单明了：BFS 的实现逻辑简单，易于理解，特别适合初学者学习。

缺点

• 空间复杂度高：与 DFS 相比，BFS 需要更多的内存，因为它同时需要存储大量的节点。
• 执行效率低：在某些情况下，BFS 可能需要访问比 DFS 更多的节点，尤其在图较为稀疏时。

8，常用几种队列说明：

1，队列（queue）只允许从队尾入队、从队头出队，不允许在中间位置插入和删除，不支持数组表示法和随机访问。使用 queue 时需要引入头文件#include<queue>。队列的基本操作包括入队、出队、取队头、判断队空、求队列大小。

• queue<int>q：创建一个空队 q，数据类型为 int。
• q.push(x)：x 入队。
• q.pop()：出队。
• q.front()：取队头（未出队）。
• q.empty()：判断队列是否为空，若为空，则返回 true。
• q.size()：求队列大小，返回队列中的元素个数。

2，deque（双端队列）是 C++ 标准模板库 (STL) 中的一个容器，它支持在两端进行高效地插入和删除操作。与队列不同的是，双端队列可以在头部和尾部进行这些操作，并且它还支持随机访问，这意味着你可以像访问数组一样通过索引来访问元素。

下面是 deque 的基本操作说明：

#include <deque>：包含 deque 的头文件。

• deque<T> dq：创建一个空的 deque 对象 dq，其中 T 是 deque 中存储的元素类型。

• dq.push_front(x)：将元素 x 插入到 deque 的前端。

• dq.push_back(x)：将元素 x 插入到 deque 的后端。

• dq.pop_front()：移除 deque 的前端元素。

• dq.pop_back()：移除 deque 的后端元素。

• dq.front()：返回 deque 的前端元素（但不移除）。

• dq.back()：返回 deque 的后端元素（但不移除）。

• dq.empty()：如果 deque 是空的则返回 true，否则返回 false。

• dq.size()：返回 deque 中元素的数量。

• dq.clear()：移除 deque 中的所有元素。

• dq.at(index) 或 dq[index]：通过索引访问 deque 中的元素。注意使用 at() 方法时，如果索引超出范围会抛出异常，而使用 [] 运算符不会检查边界。 这里是一个简单的示例来演示 deque 的使用：

这个程序创建了一个 deque，然后向其前端和后端添加了几个元素，并展示了如何移除它们以及获取 deque 的状态信息。

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    // 向 deque 的前后添加元素
    dq.push_front(5);
    dq.push_back(10);
    dq.push_front(3);

    // 输出 deque 的前端和后端元素
    cout << "Front: " << dq.front() << ", Back: " << dq.back() <<endl;

    // 移除前端和后端元素
    dq.pop_front();
    dq.pop_back();

    // 输出 deque 的大小
    cout << "Size after pop operations: " << dq.size() <<endl;

    // 检查 deque 是否为空
    if (dq.empty()) {
        cout << "Deque is empty." << endl;
    } else {
        cout << "Deque is not empty." <<endl;
    }

    return 0;
}

//bfs模板
struct Node {
	int x,y,step;
  .....
}
queue<Node> q;
void bfs() {
	标记起点 
	起点入队列 
	while(!q.empty()) {//队列不为空 
		ed nw=q.front();//返回队首
		for(拓展出接下来可能的状态) {
			ed nxt;
			记录这一状态
			判断状态是否合法 
			标记状态 
			q.push_back(nxt);//状态入队列 
		}
		q.pop_front();//弹出队首 
	}
}

---

9，BFS与DFS使用场景的区别

（1）核心区别：

dfs:

像探险家，一条路走到黑，走不通再回头换路，适合遍历所有可能。

dfs:

像雷达扫苗，一层一层向外扩散，适合找最短路径或最近解。

（2）什么时候用DFS？

典型场景：

1，要枚举所有可能的解（如排列组合、子集、拆分数）。 2，问题需要回溯（如迷宫的所有路径、数独填充）。 3，路径的深度最大多少，但不需要求最短路径。

题目：

1，数的全排列 2，n皇后问题 3，自然数的拆分 4，树的遍历

（3）什么时候用BFS？

典型场景：

1，需要找最短路径、最少操作次数（如迷宫最短路径，社交网络的最短关系链）。 2，问题的解在较浅的层次（靠近起点）。

题目：

1，走出迷宫（bfs会一层层扩散，第一次到达终点的一定是最短路径。） 2，二叉树的层次遍历。

（4）判断技巧？

三问法： 1，问题是否要求所有可能解？（是，DFS） 2，问题是否要求最短路径或最少多少步？（是,BFS) 3，问题是否可能在浅层？(是，BFS)

（5）有些情况两者均可？

比如岛屿数量问题等相关类型的题。两种解法都可。