时间戳

首页 > 解决方案 > 如何找到列表的所有路径？

java - 如何找到列表的所有路径？

问题描述

我有一个这样的列表：

[[A], [B, C, D], [E, F], [G]]

对于 Java 代码初始化：

 List<List<String>> data = new ArrayList<>();
 data.add(Arrays.asList("A"));
 data.add(Arrays.asList("B", "C", "D"));
 data.add(Arrays.asList("E", "F"));
 data.add(Arrays.asList("G"));

并希望得到如下结果：

[[A,B,E,G],[A,B,F,G], [A,C,E,G],[A,C,F,G],[A,D,E,G],[A,D,F,G]]

怎么做 ？非常感谢。

标签： javaalgorithmgraph

解决方案

你可以写一个递归算法来解决这个问题。对于每个递归调用，该算法在图中向下移动一层。它的要点是您首先计算当前所在图层下方的所有路径，然后将当前图层中的所有节点添加到这些路径中。

这里有一些伪代码可以帮助你：

paths(input) {
    if input is empty -> return empty // This is your base case

    currentNodes = input[0]
    subPaths = paths(input.tail) // Recursive call with the rest of your input

    if subPaths is empty -> return input // The paths from the last layer is itself

    result = emptyList()
    for all nodes in currentNodes
        for all paths in subPaths
            prepend node to path and add to result

    return result
}

推荐阅读