python - 如何调整 DFS 以遍历具有非唯一节点标识符的 m-ary 树？

Question

我需要在不同节点具有相同标识符的 m-ary 树上运行 DFS。此外，我需要访问所有节点，而不是树的去重版本。

假设我定义我的 m-ary 树（为简单起见这里是二进制）如下：

# the branch with parent node 2 appears twice in the tree
tree = {1: {2, 3}, 2: {4, 5}, 3: {2, 6}}
print(tree)

我通常会按如下方式实现 DFS，即考虑访问节点：

# initialize stack with root node
stack = [1]
visited = set()
# record the order
dfs = []
while stack:
    current = stack.pop()
    dfs.append(current)
    if current not in visited:
        visited.add(current)
        if current in tree:
           stack.extend(tree[current])
        else:
           # we have a leaf node
           pass

print(dfs)

这会产生以下正确但不是我想要的顺序，因为它将忽略父 2 的第二个分支出现：

[1, 3, 6, 2, 5, 4]

我可以改为忽略visited逻辑并直接执行：

# initialize stack with root node
stack = [1]
# record the order
dfs = []
while stack:
    current = stack.pop()
    dfs.append(current)
    if current in tree:
        stack.extend(tree[current])
    else:
        # we have a leaf node
        pass

print(dfs)

这会产生所需的以下顺序：

[1, 3, 6, 2, 5, 4, 2, 5, 4]

当我摆脱已访问的支票时，是否有我遗漏的边境案例？

标签： pythonalgorithm

Answer 1

visited当保证由唯一id节点形成的图形没有循环时，您的解决方案（没有）将正常工作，即它是DAG。

它只会在输出中给出重复的标识符。如果从根到某个节点有n条路径，则该节点的标识符将在输出中出现n次。请注意，如果图很密集，则可能会产生较大的输出。