代码随想录算法训练Day56|DFS理论基础、LeetCode797-所有可能的路径、BFS理论基础
dfs 与 bfs 区别
提到深度优先搜索（dfs），就不得不说和广度优先搜索（bfs）有什么区别
先来了解dfs的过程，很多录友可能对dfs（深度优先搜索），bfs（广度优先搜索）分不清。
先给大家说一下两者大概的区别：
- dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
- bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
当然以上讲的是，大体可以这么理解，接下来 我们详细讲解dfs，（bfs在用单独一篇文章详细讲解）
DFS理论基础
所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
提示：
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i] [j] < n
- graph[i] [j] != i（即不存在自环）
- graph[i] 中的所有元素 互不相同
- 保证输入为 有向无环图（DAG）
解题思路
1.确认递归函数，参数
首先我们dfs函数一定要存一个图，用来遍历的，还要存一个目前我们遍历的节点，定义为x
至于 单一路径，和路径集合可以放在全局变量，那么代码是这样的：
private List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
private List<Integer> path = new ArrayList<>(); // 0节点到终点的单一路径
// x：目前遍历的节点
// graph：存当前的图
private void dfs(int[][] graph, int x)
2.确认终止条件
什么时候我们就找到一条路径了？
当目前遍历的节点 为 最后一个节点的时候，就找到了一条，从 出发点到终止点的路径。
当前遍历的节点，我们定义为x，最后一点节点，就是 graph.length - 1（因为题目描述是找出所有从节点 0 到节点 n-1 的路径并输出）。
所以 但 x 等于 graph.size() - 1 的时候就找到一条有效路径。 代码如下：
// 要求从节点 0 到节点 n-1 的路径并输出，所以是 graph.length - 1
if (x == graph.length - 1) { // 找到符合条件的一条路径
result.add(new ArrayList<>(path));// 收集有效路径
return;
}
3.处理目前搜索节点出发的路径
接下来是走 当前遍历节点x的下一个节点。
首先是要找到 x节点链接了哪些节点呢？ 遍历方式是这样的：
for (int i = 0; i < graph[x].length; i++) { // 遍历节点n链接的所有节点
接下来就是将 选中的x所连接的节点，加入到 单一路径来。
path.add(graph[x][i]); // 遍历到的节点加入到路径中来
一些录友可以疑惑这里如果找到x 链接的节点的，例如如果x目前是节点0，那么目前的过程就是这样的：
二维数组中，graph[x] [i] 都是x链接的节点，当前遍历的节点就是 graph[x][i] 。
进入下一层递归
dfs(graph, graph[x][i]); // 进入下一层递归
最后就是回溯的过程，撤销本次添加节点的操作。 该过程整体代码：
for (int i = 0; i < graph[x].length; i++) { // 遍历节点n链接的所有节点
path.add(graph[x][i]); // 遍历到的节点加入到路径中来
dfs(graph, graph[x][i]); // 进入下一层递归
path.remove(path.size() - 1); // 回溯，撤销本节点
}
DFS
本题整体代码如下：
//dfs
class Solution {
private List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
private List<Integer> path = new ArrayList<>(); // 0节点到终点的路径
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
path.add(0); // 无论什么路径已经是从0节点出发
dfs(graph, 0); // 开始遍历
return result;
}
// x：目前遍历的节点
// graph：存当前的图
private void dfs(int[][] graph, int x) {
// 要求从节点 0 到节点 n-1 的路径并输出，所以是 graph.length - 1
if (x == graph.length - 1) { // 找到符合条件的一条路径// 从0---->3
result.add(new ArrayList<>(path));// 收集有效路径
return;
}
for (int i = 0; i < graph[x].length; i++) { // 遍历节点n链接的所有节点
path.add(graph[x][i]); // 遍历到的节点加入到路径中来 0->1 //21行回来 变成0->1->3 r 到了15行 result加入0->1->3路径 return回21，撤销
dfs(graph, graph[x][i]); // 进入下一层递归 进入节点1
path.removeLast(); // 回溯，撤销本节点
}
}
}
#总结
本题是比较基础的深度优先搜索模板题，这种有向图路径问题，最合适使用深搜，当然本题也可以使用广搜，但广搜相对来说就麻烦了一些，需要记录一下路径。
而深搜和广搜都适合解决颜色类的问题，例如岛屿系列，其实都是 遍历+标记，所以使用哪种遍历都是可以的。
至于广搜理论基础，我们在下一篇在好好讲解，敬请期待！
BFS理论基础
大家应该好奇，这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。
很多网上的资料都是直接说用队列来实现。
其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。
用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。
如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
因为栈是先进后出，加入元素和弹出元素的顺序改变了。
那么广搜需要注意 转圈搜索的顺序吗？ 不需要！
所以用队列，还是用栈都是可以的，但大家都习惯用队列了，所以下面的讲解用我也用队列来讲，只不过要给大家说清楚，并不是非要用队列，用栈也可以。
广度优先搜索BFS—模板
下面给出广搜代码模板，该模板针对的就是，上面的四方格的地图： （详细注释）
//BFS
class Solution {
private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 表示四个方向
void bfs(char[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>(); // 定义队列
queue.offer(new int[]{x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while (!queue.isEmpty()) { // 开始遍历队列里的元素
int[] cur = queue.poll(); // 从队列取元素
int curx = cur[0];
int cury = cur[1]; // 当前节点坐标
for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue; // 坐标越界了，直接跳过
if (!visited[nextx][nexty]) { // 如果节点没被访问过
queue.offer(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
}
}
}
}
}
我们使用了队列来实现BFS。起始节点被加入到队列中，并且在每次迭代中，我们从队列中取出一个节点，然后检查其周围的节点。如果一个未被访问过的节点符合条件，我们将其加入队列，并标记为已访问。这个过程一直持续到队列为空，所有的节点都被访问过为止。
ps:部分图片和代码来自代码随想录和Leetcode官网
原文地址：https://blog.csdn.net/m0_75002567/article/details/140235656
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！