枚举树中所有路径

Question

我想知道如何最好地实现树形数据结构，以便能够枚举所有级别的路径。让我用以下示例来解释一下：

     A
   /   \
   B    C
   |    /\
   D   E  F

我希望能够生成以下内容：

A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F

目前，我正在使用字典构建的数据结构上执行深度优先搜索，并记录所见过的唯一节点，但我想知道是否有更好的方法来进行这种遍历。有什么建议吗？

- Legend

---

所有的图边都是双向的吗？ - Mike Pennington

那么你也期望 b-a、c-a、d-b、e-c、f-c、a-b-a、a-c-a、b-d-b、b-a-b、b-a-c 等等吗？ - saus

@saus：抱歉，我没注意到。我的意思是方向性的。 - Legend

Answer 1

无论何时您在树上遇到问题，都可以使用递归:D

def paths(tree):
  #Helper function
  #receives a tree and 
  #returns all paths that have this node as root and all other paths

  if tree is the empty tree:
    return ([], [])
  else: #tree is a node
    root = tree.value
    rooted_paths = [[root]]
    unrooted_paths = []
    for subtree in tree.children:
        (useable, unueseable) = paths(subtree)
        for path in useable:
            unrooted_paths.append(path)
            rooted_paths.append([root]+path)
        for path in unuseable:
            unrooted_paths.append(path)
    return (rooted_paths, unrooted_paths)

def the_function_you_use_in_the_end(tree):
   a,b = paths(tree)
   return a+b

- hugomg

---

你能提供一个示例，展示使用 paths() 解决 OP 的问题时你会调用哪个 tree 吗？ - Mike Pennington

@Mike 我觉得没必要。最好是将算法适应于OP正在使用的任何数据结构，而不是尝试猜测特定的树实现方式。 - hugomg

Answer 2

再来一种方法：

树中没有重复的路径，每个路径都可以通过其起点和终点唯一描述。

因此，枚举路径的一种方法是枚举每对可能的顶点。对于每一对顶点，找到路径（找到公共祖先并穿过它）相对容易。

- maxim1000

Answer 3

使用深度优先搜索找到树中每个节点的路径，然后调用enumerate-paths(Path p)，其中p是从根节点到该节点的路径。假设路径p是节点数组p[0] [1] .. p[n]，其中p[0]是根节点，p[n]是当前节点。

enumerate-paths(p) {
    for i = 0 .. n  
        output p[n - i] .. p[n] as a path. 
}

每条路径都是不同的，与树的任何其他节点返回的结果也不同，因为没有其他路径以p[n]结尾。显然它是完整的，因为任何路径都是从一个节点到其和根节点之间的某个节点。它也是最优的，因为它找到并精确地输出每个路径。

顺序可能与您的略有不同，但您始终可以创建一个路径列表数组，其中A[x]是长度为x的路径列表。然后，您可以按其长度的顺序输出路径，尽管这将需要O(n)存储。

- Larry Watanabe