深搜(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);
}
}
}