华东民航机场建设公司网站cc在线代理

华东民航机场建设公司网站,cc在线代理,wordpress 仿简书模板,帮传销做网站所有可能的路径 问题描述 给你一个有 n 个节点的有向无环图#xff08;DAG#xff09;#xff0c;节点编号从 0 到 n - 1。给你一个二维数组 graph 表示图的邻接表#xff0c;其中 graph[i] 是一个节点数组#xff0c;表示从节点 i 出发可以到达的所有节点。 请你找出从节…所有可能的路径问题描述给你一个有n个节点的有向无环图DAG节点编号从0到n - 1。给你一个二维数组graph表示图的邻接表其中graph[i]是一个节点数组表示从节点i出发可以到达的所有节点。请你找出从节点 0 到节点 n-1 的所有路径并返回这些路径。注意图中不包含自环和平行边且保证是无环图。示例输入: graph [[1,2],[3],[3],[]] 输出: [[0,1,3],[0,2,3]] 解释: 从0到3有两条路径: 0-1-3 和 0-2-3。算法思路经典的图遍历问题核心有向无环图DAG保证不会有无限递归每条路径都是有限的路径记录需要记录从起点到当前节点的完整路径回溯算法到达终点时保存路径然后回溯继续探索其他路径方法深度优先搜索DFS 回溯广度优先搜索BFS动态规划由于需要返回所有路径而不是计数不适合代码实现方法一DFS 回溯importjava.util.*;classSolution{/** * 使用DFS和回溯找到从0到n-1的所有路径 * * param graph 邻接表表示的有向无环图 * return 所有从0到n-1的路径列表 */publicListListIntegerallPathsSourceTarget(int[][]graph){ListListIntegerresultnewArrayList();ListIntegerpathnewArrayList();// 从节点0开始DFSdfs(graph,0,path,result);returnresult;}/** * DFS回溯函数 * * param graph 邻接表 * param node 当前节点 * param path 当前路径 * param result 所有路径的结果列表 */privatevoiddfs(int[][]graph,intnode,ListIntegerpath,ListListIntegerresult){// 将当前节点加入路径path.add(node);// 如果到达目标节点n-1if(nodegraph.length-1){// 保存当前路径的副本result.add(newArrayList(path));}else{// 递归访问所有邻居节点for(intneighbor:graph[node]){dfs(graph,neighbor,path,result);}}// 回溯移除当前节点返回上一层path.remove(path.size()-1);}}方法二BFS广度优先搜索importjava.util.*;classSolution{/** * 使用BFS找到所有路径 * * param graph 邻接表 * return 所有路径 */publicListListIntegerallPathsSourceTarget(int[][]graph){ListListIntegerresultnewArrayList();inttargetgraph.length-1;// 队列存储路径而不是单个节点QueueListIntegerqueuenewLinkedList();queue.offer(Arrays.asList(0));// 初始路径只包含起点0while(!queue.isEmpty()){ListIntegercurrentPathqueue.poll();intlastNodecurrentPath.get(currentPath.size()-1);// 如果到达目标节点if(lastNodetarget){result.add(currentPath);}else{// 扩展所有可能的下一步for(intneighbor:graph[lastNode]){ListIntegernewPathnewArrayList(currentPath);newPath.add(neighbor);queue.offer(newPath);}}}returnresult;}}方法三迭代DFSimportjava.util.*;classSolution{/** * 使用显式栈实现的迭代DFS */publicListListIntegerallPathsSourceTarget(int[][]graph){ListListIntegerresultnewArrayList();inttargetgraph.length-1;// 栈存储路径StackListIntegerstacknewStack();stack.push(Arrays.asList(0));while(!stack.isEmpty()){ListIntegercurrentPathstack.pop();intlastNodecurrentPath.get(currentPath.size()-1);if(lastNodetarget){result.add(currentPath);}else{// 为了保持输出顺序与递归DFS一致需要逆序添加邻居for(intigraph[lastNode].length-1;i0;i--){intneighborgraph[lastNode][i];ListIntegernewPathnewArrayList(currentPath);newPath.add(neighbor);stack.push(newPath);}}}returnresult;}}算法分析时间复杂度O(2^N × N)在最坏情况下完全图从0到n-1的路径数可能是指数级的每条路径的长度最多为N复制路径需要O(N)时间空间复杂度DFSO(N) - 递归栈深度最多为N不包括结果存储BFSO(2^N × N) - 队列中可能存储所有路径结果存储O(2^N × N) - 所有路径的总空间算法过程1graph [[1,2],[3],[3],[]]DFS回溯开始: node0, path[] ├─ path[0] │ ├─ neighbor1: node1, path[0,1] │ │ └─ neighbor3: node3, path[0,1,3] → 到达目标保存[0,1,3] │ │ path回溯为[0,1]然后回溯为[0] │ └─ neighbor2: node2, path[0,2] │ └─ neighbor3: node3, path[0,2,3] → 到达目标保存[0,2,3] └─ 结束BFS初始队列[[0]]扩展0[[0,1], [0,2]]扩展[0,1][[0,2], [0,1,3]] → 保存[0,1,3]扩展[0,2][[0,1,3], [0,2,3]] → 保存[0,2,3]结果[[0,1,3], [0,2,3]]测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[][]graph1{{1,2},{3},{3},{}};System.out.println(Test 1: solution.allPathsSourceTarget(graph1));// [[0,1,3],[0,2,3]]// 测试用例2直接连接int[][]graph2{{1},{}};System.out.println(Test 2: solution.allPathsSourceTarget(graph2));// [[0,1]]// 测试用例3单节点int[][]graph3{{}};System.out.println(Test 3: solution.allPathsSourceTarget(graph3));// [[0]]// 测试用例4多层图int[][]graph4{{1,2},{3,4},{3,4},{5},{5},{}};System.out.println(Test 4: solution.allPathsSourceTarget(graph4));// [[0,1,3,5],[0,1,4,5],[0,2,3,5],[0,2,4,5]]// 测试用例5线性图int[][]graph5{{1},{2},{3},{4},{5},{}};System.out.println(Test 5: solution.allPathsSourceTarget(graph5));// [[0,1,2,3,4,5]]// 测试用例6星型图int[][]graph6{{1,2,3,4},{5},{5},{5},{5},{}};System.out.println(Test 6: solution.allPathsSourceTarget(graph6));// [[0,1,5],[0,2,5],[0,3,5],[0,4,5]]// 测试用例7复杂DAGint[][]graph7{{1,2},{3},{3,4},{5},{5},{}};System.out.println(Test 7: solution.allPathsSourceTarget(graph7));// [[0,1,3,5],[0,2,3,5],[0,2,4,5]]// 测试用例8两个节点无连接int[][]graph8{{},{}};System.out.println(Test 8: solution.allPathsSourceTarget(graph8));// 测试用例9起点等于终点的情况int[][]graph9{{}};// n1, 起点0终点0System.out.println(Test 9: solution.allPathsSourceTarget(graph9));// [[0]]// 测试用例10较大的图int[][]graph10{{1,2,3},{4,5},{4,5},{4,5},{6},{6},{7},{}};ListListIntegerresult10solution.allPathsSourceTarget(graph10);System.out.println(Test 10: result10.size());}关键点回溯在递归返回后移除当前节点确保不同路径之间不会相互影响路径复制保存路径时必须创建副本new ArrayList(path)否则所有保存的路径都会指向同一个List对象DAG保证是有向无环图所以不需要visited数组如果有环需要visited数组避免无限递归边界情况单节点图起点等于终点直接连接的两个节点复杂的多分支图顺序DFS会按邻接表顺序输出路径BFS会按路径长度顺序输出路径常见问题为什么不需要visited数组有向无环图DAG不可能回到已经访问过的节点什么时候需要创建路径副本每次找到完整路径并要保存到结果中时因为path对象会在回溯过程中被修改BFS和DFS的输出顺序有什么区别DFS按深度优先的顺序通常与邻接表顺序一致BFS按路径长度顺序先输出较短路径