BFS，DFS搜索需要标记为已访问树木？

Question

查看BFS和DFS算法，它们似乎将节点标记为已访问。如果我只在树中导航，我的实现是否仍然需要将节点标记为已访问？我想对每个节点执行一次操作。

它似乎只适用于存在循环的图形，这样我就有可能两次碰到同一个节点。如果我递归地对一棵树进行调用，那么似乎不需要具有已访问状态，因为在堆栈中的所有调用返回到当前节点之后，我可以选择在节点上执行我想要的操作。我的假设正确吗？

谢谢

Answer 1

这是一种简单的递归方法来执行DFS算法：

def dfs(node):
    """Depth First Search Algorithm"""
    if not node or node.visited:
        return

    node.visited = True

    dfs(node.below)
    dfs(node.right)
    dfs(node.above)
    dfs(node.left)

Answer 2

您的假设是正确的，标记只在有周期的数据结构中才需要，因为树没有周期-您可以从实现中删除标记部分，BFS/DFS应该仍然有效！

例如：按顺序遍历树实际上是运行一个带有额外“规则”的DFS，即您总是首先访问左边的孩子。

Python：

def in-order(node):
    if not node:
        return
    in-order(node.get_left())
    print(node)
    in-order(node.get_right())

Answer 3

对于定向树，您的假设是正确的。

对于无向树-如果选择不标记所有访问的节点-则应在递归中发送一个附加变量，该变量将告诉当前节点的哪个邻居已被遍历（DFS遍历中的父节点）。

例如Python中的DFS（无向树）：

def dfs(curr_node, parent):
    for node in getNeighbors(curr_node):
        if node!=parent:
            dfs(node)

然而，BFS是迭代完成的，在无向情况下，您不能避免标记。