深度优先搜索理论基础及习题797.所有可能的路径

习题797.所有可能的路径"/>

深度优先搜索理论基础及习题797.所有可能的路径

深搜（dfs）和广搜的区别（bfs）

dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
dfs代码框架
dfs需要用到回溯

void dfs(参数) {if (终止条件) {存放结果;return;}for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果}
}

深搜三部曲
1.确认递归函数，参数
2.确认终止条件
终止添加不仅是结束本层递归，同时也是我们收获结果的时候。另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了， 下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归
3.处理目前搜索节点出发的路径

for (选择：本节点所连接的其他节点) {处理节点;dfs(图，选择的节点); // 递归回溯，撤销处理结果
}

797. 所有可能的路径

题目：给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
题目链接：797. 所有可能的路径

class Solution {private List<List<Integer>> result=new ArrayList<>();private List<Integer> onepath=new ArrayList<Integer>();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {onepath.add(0);dfs(0,graph);return result;}public void dfs(int node,int[][] graph){if(node==graph.length-1){List<Integer> oneresult=new ArrayList<Integer>(onepath);result.add(oneresult);}for(int j=0;j<graph[node].length;j++){onepath.add(graph[node][j]);dfs(graph[node][j],graph);onepath.remove(onepath.size()-1);}}
}