DFS & BFS 搜索 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # DFS 与 BFS ## DFS 深度优先遍历略。 ## BFS 广度优先遍历 ![[_attachment/00-数据结构与算法笔记/专题总结/DFS & BFS 搜索.assets/IMG-DFS & BFS 搜索-623BA5F53E79BA14E625A25070945B1C.png|470]] 在无权图中，BFS 以层序遍历，**每一层代表 "一步"**，因此 **BFS 首次访问某一位置时，即可得到从源点到该位置的最少步数**。 # DFS 与 BFS 复杂度分析给定图 $G=(V,E)$ ： - 采用 **==邻接表==建图** 时： - 时间复杂度：$O(|V|+|E|)$，图中**每个顶点会访问一次**，然后 **==枚举各顶点的每条边==**，故**每条边也最多被访问一次**。 - 空间复杂度：$O(|V|+|E|)$ ，存储 V 个顶点以及所有边。 - 采用 **==邻接矩阵==建图** 时： - 时间复杂度：$O(|V|^2)$，图中**每个顶点会访问一次**，然后**枚举图中所有顶点**，检查是否存在边。 - 空间复杂度：$O(|V|^2)$ 图可以是 **无向图** 或 **有向图**。 > [!NOTE] 从一个顶点出发进行 DFS/BFS，搜索整个连通分量 > > 在 "**不访问重复顶点**" 的情况下地**走一遍**可得到： > > - **图的生成树/支撑树**（一个 **==极大连通分量==**） > - 会 **==访问到所有顶点==而得到生成树**； > - **不一定会 "==走过==" 所有边，但一定会 "==见过==" 所有边**！=> 每一步都会**为每个顶点遍历其邻接边** > > - 若能够遇见 "**已访问过的顶点**" ，意味着**图中存在环**（从一个顶点出发，到另一个顶点存在两条路径） # DFS 实现模版 DFS 有两种写法，差别在于 "**对将访问位置的合法性检查的时机**" : 1. 写法一：在 "**==DFS 函数体内==**" 首先进行位置合法性检查； 2. 写法二：在 "**==调用 DFS 之前==**" 先进行位置合法性检查，确保传递给 `dfs()` 的是有效位置。 > [!NOTE] 建议：`DFS` 函数体内始终先进行 "可行性" 检查，独立于外部判断。 ![[_attachment/00-数据结构与算法笔记/专题总结/DFS & BFS 搜索.assets/IMG-DFS & BFS 搜索-85EAD0388F614795BE1FF7D90D6E2C86.png|347]] #### 一般图 DFS ```cpp // 一般图上DFS void dfs(vector<vector<int>>& graph, int start, int dest) { // graph是邻接表. int n = graph.size(); vector<bool> visited(n, false); auto dfs = [&](auto& self, int u) { if (visited[u]) return; // 若保证传入DFS的都是未访问的有效位置, 则可省略. visited[u] = true; // process(u); if (u == dest) return; // 抵达终点 for (const int v : graph[u]) { if (visited[v]) continue; self(self, v); } // visited[u] = false; // opt.可选, 撤销对已访问位置的标记, 适用于回溯的情况 }; dfs(dfs, start); } ``` #### 网格图 DFS ```cpp // 网格图DFS class DFS_Grid { static constexpr int dirs[4][2]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 递归实现 static void DFS(vector<vector<int>>& grid, int sx, int sy) { int m = grid.size(), n = grid[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); auto dfs = [&](auto& self, int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n) return; if (visited[x][y]) return; visited[x][y] = true; // process(x, y); for (const auto [dx, dy] : dirs) { self(self, x + dx, y + dy); } // visited[x][y] = false; // opt.可选, 撤销对已访问位置的标记, 适用于回溯的情况 }; dfs(dfs, sx, sy); } // 迭代+栈实现. static void DFS_by_iter(vector<vector<int>> &graph, int sx, int sy) { if (graph.empty()) return; int m = graph.size(), n = graph[0].size(); if (sx < 0 || sx >= m || sy < 0 || sy >= n) return; stack<pair<int, int>> s({{sx, sy}}); vector<vector<bool>> visited(m, vector<bool>(n, false)); visited[sx][sy] = true; // 入栈时就必须标记已访问. while (!s.empty()) { auto [x, y] = s.top(); s.pop(); // process(graph, x, y); for (const auto& [dx, dy]: dirs) { // 遍历各个方向 int nx = x + dx, ny = y + dy; // 邻居节点坐标 if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (visited[nx][ny]) continue; visited[x][y] = true; // 入栈时就必须标记已访问, 避免重复入栈. s.emplace(nx, ny); // 邻居节点入栈 } } } }; ``` # BFS 实现模版 > [!caution] BFS 必须在 "**==顶点入队时==**" 就立即标记 `visited` 已访问，否则会**导致同一顶点==多次重复地入队==**！（力扣上会直接超时） > > 即 `visited[v] = true` 必须紧邻 "邻居节点入队" 的位置！ > > ![[_attachment/00-数据结构与算法笔记/专题总结/DFS & BFS 搜索.assets/IMG-DFS & BFS 搜索-4982087C1B13B3815864992DC6105F8F.png|627]] ### 一般图中 BFS ```cpp // 基础BFS. void bfs(vector<vector<int>>& graph, int start) { // graph是邻接表. int n = graph.size(); vector<bool> visited(n, false); queue<int> que{{start}}; // que记录已标记访问的节点, 这些节点的邻居待访问 visited[start] = true; while (!que.empty()) { int u = que.front(); que.pop(); for (const int v : graph[u]) { if (visited[v]) continue; visited[v] = true; que.emplace(v); // process(graph, v); // 处理顶点. } } } ``` ### 网格图上 BFS ```cpp // 基础BFS. void bfs(vector<vector<int>>& grid, int sx, int sy) { // `起点(sx, sy)` static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int m = grid.size(), n = grid[0].size(); if (m == 0 || n == 0) return; if (sx < 0 || sx >= m || sy < 0 || sy >= n) return; // 初始时, 将起点加入栈, 并标记起点为"已访问" // queue中存储的必须是合法的、下一步待访问的位置. 因此初始时, 需要对(sx,sy)非法的情况特判. vector<vector<bool>> visited(m, vector<bool>(n, false)); queue<pair<int, int>> que({{sx ,sy}}); // que记录已标记访问的节点, 这些节点的邻居待访问 visited[sx][sy] = true; while (!que.empty()) { auto [x, y] = que.front(); que.pop(); for (const auto& [dx ,dy] : dirs) { int nx = x + dx, ny = y + dy; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (visited[nx][ny]) continue; if (grid[nx][ny] == 1) continue; // 障碍物, 不可访问. visited[nx][ny] = true; // 一旦入队列, 需立即标记"已访问". 防止同一位置被多次重复入队. que.emplace(nx, ny); // process(graph, nx, ny); // 处理该位置 } } } ``` #### 🚨 非常低效的实现 ```cpp // 错误实现: 差评, 非常低效, 会导致大量节点重复加入队列, void bfs(vector<vector<int>> grid, int start_x, int start_y) { int m = grid.size(), n = grid[0].size(); const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; queue<pair<int, int>> q; vector<vector<bool>> visited(m, vector<bool>(n, false)); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (visited[nx][ny]) continue; if (grid[nx][ny] == 1) continue; // 障碍物, 不可访问 // 标记访问(nx, ny), 将该位置加入搜索. visited[nx][ny] = true; for (auto [dx, dy] : dirs) { int nx = x + dx, ny = y + dy; q.emplace(nx, ny); } } } ``` # 回溯法 > 回溯（backtracking）：**穷举式的搜索算法**。回溯算法本质上就是 "**==DFS==**"：**采用试错的思想**，在搜索尝试过程中寻找问题的解，**无法进一步搜索时**则 "**回退**"，转而搜索其他路径。 > [!NOTE] 回溯法适用的问题： > > - **组合问题**：n 个数中找出满足条件的k 个数的集合 > - **子集问题**：n 个数中有多少满足条件的子集 > - **排列问题**：n 个数按一定规则排列，所有可能的排列方式 > - **切割问题**：一个字符串按指定规则切割，有多少种切割方式 > - **棋盘问题**：解数独、N 皇后 > - **路径问题**：找出**所有满足条件的路径** > [!example] 全排列问题的搜索树 > 参见 [[^1]] > ![[_attachment/00-数据结构与算法笔记/专题总结/DFS & BFS 搜索.assets/IMG-DFS & BFS 搜索-915B2A1775E3586DD2816B3D2501CD9D.png|524]] ## 回溯法模版参见 [^1] ```cpp void backtracking(参数) { if (终止条件) { 存放结果; return; } for (枚举当前可选的元素列表) { 处理节点, 合法性检查; backtracking(路径，选择列表); // 递归回溯，撤销处理结果; } } ``` > [!NOTE] 注意 DFS 中对 "位置合法性检查" 的两种写法风格，体现在 "**回溯**" 如下。上述的回溯模版是**风格 2**。 ```cpp // 风格一: void dfs(int u) { if (节点u不可达) return; // 记录节点u在当前路径上 path.push_back(u); if (u为目标终点) { ans.push_back(path); path.pop_back(); // 回撤 } // 2.找邻居 for (节点u的各个邻居v) { dfs(v); } // 撤回对节点u的记录 path.pop_back(); } // 风格二: 要求外部调用dfs前先将起点s加入path. void dfs(int u) { if (u为目标终点) ans.push_back(path); for (节点u的各个邻居v) { if (节点v可达) { // 记录节点v在当前路径上 path.push(v); dfs(v); // 撤回对节点v的记录 path.pop(); } } } ``` # 参考资料 # Footnotes [^1]: [01. 回溯算法知识 \| 算法通关手册（LeetCode）](https://algo.itcharge.cn/09.Algorithm-Base/04.Backtracking-Algorithm/01.Backtracking-Algorithm/#_2-%E4%BB%8E%E5%85%A8%E6%8E%92%E5%88%97%E9%97%AE%E9%A2%98%E5%BC%80%E5%A7%8B%E7%90%86%E8%A7%A3%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95)