专注网站制作,煤棚网架多少钱一平方,网站标题关键词用什么隔开,凡科网建站入门教程题目
一个有向无环图由n个节点#xff08;标号从0到n-1#xff0c;n≥2#xff09;组成#xff0c;请找出从节点0到节点n-1的所有路径。图用一个数组graph表示#xff0c;数组的graph[i]包含所有从节点i能直接到达的节点。例如#xff0c;输入数组graph为[[1#xff0c…题目
一个有向无环图由n个节点标号从0到n-1n≥2组成请找出从节点0到节点n-1的所有路径。图用一个数组graph表示数组的graph[i]包含所有从节点i能直接到达的节点。例如输入数组graph为[[12][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}, {}};ListListInteger result allPathsSourceTarget(graph);System.out.println(result);}public static ListListInteger allPathsSourceTarget(int[][] graph) {ListListInteger result new LinkedList();ListInteger path new LinkedList();dfs(0, graph, path, result);return result;}private static void dfs(int source, int[][] graph, ListInteger path, ListListInteger 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);}}
