力扣 797. 所有可能路径【DFS】
1. 题目
2. 代码
- DFS ， 直接见代码
class Solution {
public:
vector<int> path;
vector<vector<int>> res; // 结果集
void dfs(vector<vector<int>>& graph, int cur, int n){
// 找出所有从节点 0 到节点 n-1 的路径
// 下标从 0 开始的
if (cur == n){ // 当前点到了终点
// 说明找到了一条路径, 收集起来
res.push_back(path);
// 返回
return ;
}
// 当前节点下面有什么边连着
for (const auto& cc : graph[cur]){
path.push_back(cc); // 收集这个节点
// 沿着这条路径递归
dfs(graph, cc, n);
path.pop_back(); // 回溯
}
return ;
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
// dfs
// 邻接表
// 从第一个节点出发
path.push_back(0);
dfs(graph, 0, graph.size() - 1);
return res;
}
};