四川网站推广,php 打开网站,建设网站公司哪里好相关的热搜问题,济宁seo公司. - 力扣#xff08;LeetCode#xff09;
给你一个有 n 个节点的 有向无环图#xff08;DAG#xff09;#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出#xff08;不要求按特定顺序#xff09; graph[i] 是一个从节点 i 可以访问的所有节点的列表#xff0…. - 力扣LeetCode
给你一个有 n 个节点的 有向无环图DAG请你找出所有从节点 0 到节点 n-1 的路径并输出不要求按特定顺序 graph[i] 是一个从节点 i 可以访问的所有节点的列表即从节点 i 到节点 graph[i][j]存在一条有向边。
即给定邻接表求0到n-1的所有路径。 自己的代码dfs来到当前节点先记录其路径。如果发现当前节点为最后节点则直接返回。否则对当前节点的每个邻接节点不断dfs。dfs完成后将当前节点从路径中删除并返回。
注意此题无需判断节点是否访问过因为本题是有向图对于某个节点指向该节点可能有好几个节点所以如果该节点只被访问一次无法得到所有路径。
class Solution {
public:vectorvectorintres;vectorvectorint allPathsSourceTarget(vectorvectorint graph) {vectorint visited(graph.size(),0),path;dfs(graph,0,path,visited);return res;}void dfs(vectorvectorint graph,int cur,vectorint path,vectorintvisited){path.push_back(cur);if(curgraph.size()-1){res.push_back(path);path.pop_back();return;}for(int i0;igraph[cur].size();i){//if(!visited[graph[cur][i]])dfs(graph,graph[cur][i],path,visited);}//visited[cur]1;path.pop_back();}
}; 官方题解
我们可以使用深度优先搜索的方式求出所有可能的路径。具体地我们从 0 号点出发使用栈记录路径上的点。每次我们遍历到点 n−1就将栈中记录的路径加入到答案中。
特别地因为本题中的图为有向无环图DAG\text{DAG}DAG搜索过程中不会反复遍历同一个点因此我们无需判断当前点是否遍历过。 class Solution {
public:vectorvectorint ans;vectorint stk;void dfs(vectorvectorint graph, int x, int n) {if (x n) {ans.push_back(stk);return;}for (auto y : graph[x]) {stk.push_back(y);dfs(graph, y, n);stk.pop_back();}}vectorvectorint allPathsSourceTarget(vectorvectorint graph) {stk.push_back(0);dfs(graph, 0, graph.size() - 1);return ans;}
}; 整体思路差不多。
