代码随想录算法训练营第60期第五十三天打卡

        大家好，我们今天来到了最后一章图论，其实图论比较难，涉及的算法也比较多，今天比较重要的就是深度优先搜索与广度优先搜索，后面的迪杰斯特拉算法等算法在我们求最短路都会涉及到，还有最近公共祖先，并查集等问题后面都会讲到，我们今天主要就看深搜与广搜的理论基础并且用这两种算法解决一道所有可达路径的问题。

第一部分深度优先搜索理论基础

        其实我们主要会涉及两种搜索算法，深搜(dfs)与广搜(bfs)，我们首先要区分这两种算法，我们就先看看区别在哪里，首先告诉大家dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。其实我比较喜欢使用深搜，当然不排除有的题目只能使用广搜才可以解决，印象中我们代码随想录的后面就有一道叫做字符串接龙的问题，那道题目似乎就只能使用广度优先搜索解决，而bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

        其实在图上可以更加直观地显示两种搜索算法的区别：

       如果我们要搜索从起点到终点的所有路径，我们就先找到目的地6随后回溯更换方向，具体的路径大家可以去代码随想录网站去看，我就不再展示了，其实大家理解就是一条路走到黑，知道遇到终止条件。

       接下来我们就一起看看深搜三部曲，第一步确认递归函数，参数，通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。一般情况，深搜需要 二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。其实我们今天的题目就有这种使用二维数组来保存路径的题目，第二步确认终止条件，终止条件很重要，很多同学写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。我们一般写深搜的时候我们一般会先写终止条件，终止添加不仅是结束本层递归，同时也是我们收获结果的时候。我们这时候其实就是收获路径的时候，如果说我们使用二维数组来存储路径那么这个时候我们就可以找到一条完整的路径，我们就把这一条路径添加到二维数组里，第三步处理目前搜索节点出发的路径，这个或许就是深搜地精华，每一道题目都有特色，后面我们会讲解很多岛屿类的问题我们就会发现每一个题目都会有特色。

       关于深搜理论基础我大概就讲解这么多，剩下的我们就借助题目来理解。接下来我们看广搜的理论基础。

第二部分广度优先搜索理论基础

        广搜（bfs）是一圈一圈的搜索过程，和深搜（dfs）是一条路跑到黑然后再回溯。其实在树里面，我们对二叉树比较了解，其实广搜大家可以理解为层序遍历，因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。这一点很重要，只要我们使用广搜搜索到的路径就一定会是最短路径，然，也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

        其实如实告诉大家，我一般不适用广搜，我比较喜欢使用深搜，但是广搜我也必须要会，我们具体来看看广搜是如何解决具体题目的，我们就直接看看代码框架，其实我还是把示意图放到下面：

       其实大家可以很清楚看到我们是一圈一圈来搜索的，接下来我们来看代码框架，我们可以考虑使用队列，因为考虑到队列先进先出的特性我们不需要一圈逆时针一圈顺时针，如果我们使用栈的话，我们就必须一圈顺时针一圈逆时针，有时候很容易出错，

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; // 只要加入队列立刻标记，避免重复访问}}}}

       上面是一个代码模板，我后面会给大家重点讲解，我们是使用队列来实现。大家先做了解，我们接下来就看一道具体的题目，我先使用深搜给大家解释一遍后面的题目有的我会使用广搜。

第三部分例题对应卡码网编号98的所有可达路径

        废话不多说，我们就直接看看题目要求：

       我们就是搜索可达路径，其实我们也很清楚一点这道题目我们是规定好了边，其实我们就需要存图，这里我先告诉大家存图的话主要有两种方式，一种是邻接表一种是邻接矩阵，我们这里就使用邻接矩阵来存储，我们就先使用深搜来解决，我们是从节点1出发最后到节点n，我们要找到所有的可达路径，我们就需要一个一维数组来存储我们当前搜索到的路径，我们使用一个二维数组来存储我们搜索好的路径，我们到达终止条件的话就到了我们收获路径的时候，我就直接先给出大家深搜的解题代码，对了大家注意我们以后图论的题目大多使用ACM模式我们要注意输出格式，这里与力扣不一样了，力扣只需要我们写出核心代码，而我们在这里要写出完整的代码：

#include <iostream>
#include <vector>using namespace std;vector<vector<int>> result;
vector<int> path;void dfs(const vector<vector<int>> &grid, int x, int n)
{if (x == n){result.push_back(path);return;}for (int i = 1; i <= n; ++i){if (grid[x][i] == 1){path.push_back(i);dfs(grid, i, n);path.pop_back();}}
}int main()
{int n,m; cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0));while(m--){int s, t; cin >> s >> t;grid[s][t] = 1;}path.push_back(1);dfs(grid, 1, n);if (result.size() == 0) cout << -1 << '\n';for (const vector<int> &pa: result){for (int i = 0; i < pa.size(); ++i){if (i > 0) cout << " ";cout << pa[i];}cout << '\n';}return 0;
}

        接下来我们使用邻接表来解决这道题目：

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径void dfs (const vector<list<int>>& graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i : graph[x]) { // 找到 x指向的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯，撤销本节点}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}path.push_back(1); // 无论什么路径已经是从0节点出发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;}
}

       其实这道题目不适合广搜来实现，后面的题目我会考虑使用广搜实现，广搜主要是解决最短路径的问题，这道题目我就分享到这里。

今日总结

      今天我们初次接触了深搜与广搜，我们大致了解了这两宗搜索算法的不同点，我们尝试使用深搜来解决所有可达路径的问题，大家多看看就可以，这个并不难理解，我们下次再见！最后祝大家端午节快乐！