回溯算法其实就是深搜,只不过这里的深搜是侧重于在图上搜索,回溯大多是在树上搜索。
797.所有可能的路径
完成
代码
模板题
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
// 搜索以node为根的图
public void dfs(int[][] graph, int node) {
if(node == graph.length-1){
res.add(new ArrayList<>(path));
return;
}
// 遍历和node直连的所有节点
for(int index = 0; index < graph[node].length; index++){
path.add(graph[node][index]);
dfs(graph, graph[node][index]);
path.removeLast();
}
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
path.add(0);
dfs(graph, 0);
return res;
}
}