题目

一个有向无环图由n个节点（标号从0到n-1，n≥2）组成，请找出从节点0到节点n-1的所有路径。图用一个数组graph表示，数组的graph[i]包含所有从节点i能直接到达的节点。例如，输入数组graph为[[1，2]，[3]，[3]，[]]，则输出两条从节点0到节点3的路径，分别为0→1→3和0→2→3。

分析

由于这个题目要求列出从节点0到节点n-1的所有路径，因此深度优先搜索是更合适的选择。
当从节点i出发能够抵达的所有节点都搜索完毕之后，将回到前一个节点搜索其他与之相邻的节点。在回到前一个节点之前，需要将节点i从路径中删除。

解

public class Test {public static void main(String[] args) {int[][] graph = {{1, 2}, {3}, {3}, {}};List<List<Integer>> result = allPathsSourceTarget(graph);System.out.println(result);}public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {List<List<Integer>> result = new LinkedList<>();List<Integer> path = new LinkedList<>();dfs(0, graph, path, result);return result;}private static void dfs(int source, int[][] graph, List<Integer> path, List<List<Integer>> result) {path.add(source);if (source == graph.length - 1) {result.add(new LinkedList<>(path));}else {for (int next : graph[source]) {dfs(next, graph, path, result);}}path.remove(path.size() - 1);}}