algorithm - 枚举树中的所有路径

Question

我试了又试；搜索和搜索，但无法真正找到解决我的问题的算法。我想枚举树中的所有路径，(不仅仅是简单路径)那些以叶节点开始和结束的路径(尽管这是一个简单的约束)。

例如，对于一棵树；

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

我希望能够生成以下路径:

4
4-2-5
4-2-5-2-1-3-6
4-2-5-2-1-3-7
4-2-5-2-1-3-6-3-7
4-2-1-3-6
4-2-1-3-7
4-2-1-3-6-3-7
5
5-2-1-3-6
5-2-1-3-7
5-2-1-3-6-3-7
6
6-3-7
7

我想这就是全部。

我尝试了以下解决方案 Complexity of finding all simple paths using depth first search? .但是，这只能找到简单的路径，因此无法找到诸如 4-2-5-2-1-3-6 之类的路径。

您有什么方法可以指导我，也许是什么算法？

Answer 1

像 4-2-1-2-5 这样的路径算吗？如果是这样，我想我有答案了:

在我看来，您只希望每条边都被访问“一次”。因此，以图形的“对偶”为例，将路径视为一系列边而不是一系列顶点。这样，边成为您的“顶点”，顶点成为“边”。

这应该会将您的问题简化为生成图形的简单路径，这是您已经知道如何解决的问题。

traverse(path, edg):
    mark edg as visited
    print path
    for each edge (e2) sharing a vertex with edg:
        traverse(e2, path+e2)

(with some sort of precaution to avoid duplicate paths being printed)