算法题所有可能的路径-洪萨配资

所有可能的路径

问题描述

给你一个有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的路径列表 */publicList<List<Integer>>allPathsSourceTarget(int[][]graph){List<List<Integer>>result=newArrayList<>();List<Integer>path=newArrayList<>();// 从节点0开始DFSdfs(graph,0,path,result);returnresult;}/** * DFS回溯函数 * * @param graph 邻接表 * @param node 当前节点 * @param path 当前路径 * @param result 所有路径的结果列表 */privatevoiddfs(int[][]graph,intnode,List<Integer>path,List<List<Integer>>result){// 将当前节点加入路径path.add(node);// 如果到达目标节点（n-1）if(node==graph.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 所有路径 */publicList<List<Integer>>allPathsSourceTarget(int[][]graph){List<List<Integer>>result=newArrayList<>();inttarget=graph.length-1;// 队列存储路径，而不是单个节点Queue<List<Integer>>queue=newLinkedList<>();queue.offer(Arrays.asList(0));// 初始路径只包含起点0while(!queue.isEmpty()){List<Integer>currentPath=queue.poll();intlastNode=currentPath.get(currentPath.size()-1);// 如果到达目标节点if(lastNode==target){result.add(currentPath);}else{// 扩展所有可能的下一步for(intneighbor:graph[lastNode]){List<Integer>newPath=newArrayList<>(currentPath);newPath.add(neighbor);queue.offer(newPath);}}}returnresult;}}

方法三：迭代DFS

importjava.util.*;classSolution{/** * 使用显式栈实现的迭代DFS */publicList<List<Integer>>allPathsSourceTarget(int[][]graph){List<List<Integer>>result=newArrayList<>();inttarget=graph.length-1;// 栈存储路径Stack<List<Integer>>stack=newStack<>();stack.push(Arrays.asList(0));while(!stack.isEmpty()){List<Integer>currentPath=stack.pop();intlastNode=currentPath.get(currentPath.size()-1);if(lastNode==target){result.add(currentPath);}else{// 为了保持输出顺序与递归DFS一致，需要逆序添加邻居for(inti=graph[lastNode].length-1;i>=0;i--){intneighbor=graph[lastNode][i];List<Integer>newPath=newArrayList<>(currentPath);newPath.add(neighbor);stack.push(newPath);}}}returnresult;}}

算法分析

时间复杂度：O(2^N × N)
- 在最坏情况下（完全图），从0到n-1的路径数可能是指数级的
- 每条路径的长度最多为N，复制路径需要O(N)时间
空间复杂度：
- DFS：O(N) - 递归栈深度最多为N，不包括结果存储
- BFS：O(2^N × N) - 队列中可能存储所有路径
- 结果存储：O(2^N × N) - 所有路径的总空间

算法过程

1：graph = [[1,2],[3],[3],[]]

DFS回溯：

开始: node=0, path=[] ├─ path=[0] │ ├─ neighbor=1: node=1, path=[0,1] │ │ └─ neighbor=3: node=3, path=[0,1,3] → 到达目标，保存[0,1,3] │ │ path回溯为[0,1]，然后回溯为[0] │ └─ neighbor=2: node=2, path=[0,2] │ └─ neighbor=3: node=3, 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){Solutionsolution=newSolution();// 测试用例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={{}};// n=1, 起点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},{}};List<List<Integer>>result10=solution.allPathsSourceTarget(graph10);System.out.println("Test 10: "+result10.size());}