题目
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
解法分析
- 使用图的深度优先（dfs）搜索进行题解
- 图的存储形式：邻接矩阵和邻接表
邻接矩阵
// 1. 创建一个 n×n 的二维数组，全部元素初始化为0
vector<vector<int>> graph(n, vector<int>(n, 0));
// 2. 输入 m 个边
while(m--){
cin >> s >> t;
// 使用邻接矩阵，1 表示节点 s 指向节点 t
graph[s][t] = 1;
}
邻接表
// 1. 构造一个数组，数组中的元素需要是列表
// 有 n 个节点，所以大小需要为 n
vector<list<int>> graph(n);
// 2. 输入 m 个边
while(m--){
cin >> s >> t;
// 使用邻接表，表示 s 和 t 是相连的
graph[s].push_back(t);
}
C语言写法
// 深度优先搜索 dfs
class Solution {
public:
vector<vector<int>> result; // 存储所有路径
vector<int> path; // 存储单个可能的路径
void dfs(const vector<vector<int>> &graph, int x, int n){
if(x == n) {
result.push_back(path);
return;
}
for(auto &i : graph[x]){
path.push_back(i); // 将当前节点加入路径
dfs(graph, i, n); // 递归
path.pop_back(); // 回溯当前节点
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
path.push_back(0);
cout << graph.size() << endl;
// 注意是size - 1 ，因为从 0 开始
dfs(graph, 0, graph.size() - 1);
return result;
}
};
