Given a directed acyclic graph (DAG) of n
nodes labeled from 0
to n - 1
, find all possible paths from node 0
to node n - 1
and return them in any order.The graph is given as follows: graph[i]
is a list of all nodes you can visit from node i
(i.e., there is a directed edge from node i
to node graph[i][j]
).
Example 1:
Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
这道题的需求就是从0节点开始依次遍历到最后一个节点,并求出所有的路径,为了求出所有的路径一般选择递归的方式,而且这题的数据没有节点遍历的死循环(即0->1 1->0),所有节点都会指向下一个不重复的节点,这样就需要额外
的判断了。
递归终止条件就是检索到最后一个节点,然后把路径记录下来。
class Solution { private: int end=0; public: vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { // 记录所有的paths 利用递归 // 所有路径都从0节点开始 // 在每个节点中循环去寻找下一个节点 最终如果找到end节点 则退出 end=graph.size()-1; vector<vector<int>> res; vector<int> dp; digui(0,res,dp,graph); return res; } void digui(int point,vector<vector<int>>&res,vector<int>dp,vector<vector<int>>& graph) { dp.push_back(point); //填充当前节点 if(point==end){ res.push_back(dp); return; } vector<int> nums=graph[point]; for(auto nn:nums){ digui(nn,res,dp,graph); } return; } };