1

我已经尝试过；搜索和搜索，但无法真正找到解决我问题的算法。我想枚举一棵树中的所有路径，（不仅仅是简单的路径）那些以叶节点开始和结束的路径（虽然这是一个简单的约束）。

例如，对于一棵树；

      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

我想就是这样。

我尝试了以下解决方案使用深度优先搜索查找所有简单路径的复杂性？. 但是，这只能找到简单的路径，因此无法找到诸如 4-2-5-2-1-3-6 之类的路径。

有什么方法可以指导我，或者任何算法？

4

2 回答 2

0

像 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)
于 2011-05-01T15:32:08.340 回答
0

如果你的树是二叉树，这里有一个相当简单的递归算法。在 Python 中：

def lchild(u):
    return 2 * u

def rchild(u):
    return 2 * u + 1

def paths(u, depth):
    if depth <= 0:
        yield ((), (u,), ())
    else:
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            yield ((u,) + ldown, lpath, lup + (u,))
        for ldown, lpath, lup in paths(lchild(u), depth - 1):
            for rdown, rpath, rup in paths(rchild(u), depth - 1):
                yield ((u,) + ldown, lpath + lup + (u,) + rdown + rpath, rup + (u,))
        for rdown, rpath, rup in paths(rchild(u), depth - 1):
            yield ((u,) + rdown, rpath, rup + (u,))

if __name__ == '__main__':
    for down, path, up in paths(1, 2):
        print path
于 2011-05-01T19:34:13.267 回答