需要 BFS、DFS 搜索将树标记为已访问？

Question

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

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

谢谢。

Answer 1

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

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

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

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

然而，BFS 是迭代完成的，并且您无法避免在无向情况下进行标记。