代码随想录算法训练营day50 | 深度优先搜索理论基础、98. 所有可达路径、广度优先搜索理论基础
碎碎念：
参考：代码随想录
深度优先搜索理论基础
dfs与bfs的区别
深度优先搜索dfs： 是从一个节点开始，尽可能深入到每个分支的尽头，然后回溯到上一个节点，再探索其他未探索的分支。通常用递归或者栈实现。
广度优先搜索bfs： 从一个节点开始，先探索所有邻接节点，然后再探索这些邻接节点的邻接节点，逐层展开。通常使用队列来实现。
dfs代码框架
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}
深搜三部曲
- 确认递归函数
- 确认终止条件
- 处理目前搜索节点出发的路径
98. 所有可达路径
题目链接
98. 所有可达路径
思想
本题应该用深度优先搜索。
深搜三部曲：
- 确定递归函数和返回参数：用一个二维数组存结果，用一个一维数组存path，返回值为空，参数需要输入要处理的图，目前遍历的节点x，总的节点个数n。
- 确定终止条件：当x==n的适合就说明找到了一条路径，需要收获结果到result，return
- 处理目前搜索节点出发的路径：遍历节点x链接的所有节点，将节点加入路径，进入下一次递归，回溯（撤销加入的节点。）
题解
#include <iostream>
#include<vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;void dfs (const vector<vector<int>>& graph, int x, int n) {if (x == n) {result.push_back(path);return;}for (int i = 1; i <= n; i++) {if (graph[x][i] == 1) {path.push_back(i);dfs(graph, i, n);path.pop_back();}}
}int main() {int n, m, s, t;cin >> n >> m;vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));while (m --) {cin >> s >> t;graph[s][t] = 1;}path.push_back(1);dfs(graph, 1, n);if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa :result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1] << endl;}
}
def dfs(graph, x, n, path, result):if x == n:result.append(path.copy())returnfor i in range(1, n + 1):if graph[x][i] == 1:path.append(i)dfs(graph, i, n, path, result)path.pop()def main():n, m = map(int, input().split())graph = [[0] * (n + 1) for _ in range(n + 1)]for _ in range(m):s, t = map(int, input().split())graph[s][t] = 1result = []dfs(graph, 1, n, [1], result)if not result:print(-1)else:for path in result:print(' '.join(map(str, path)))if __name__ == "__main__":main()
反思
注意体会ACM模式对输入输出的控制。
广度优先搜索理论基础
广度优先搜索的使用场景
广搜适合解决两个点之间的最短路径问题。因为广度优先搜索是从起点出发，以起点为中心一圈一圈搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。只要搜到终点一定是最短路径。
代码框架
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素int curx = cur.first;int cury = cur.second; // 当前节点坐标for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历int nextx = curx + dir[i][0];int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问}}}}