python - 用于查找两个节点之间是否存在路由的 DFS

Question

我正在尝试实现 DFS，但在这方面遇到了一些麻烦。

首先，我设法得到了一个简单的 DFS 示例，它只在访问节点时打印出节点。

def DFS_helper(self, node, visited):
    if node == None:
        return

    print(node.val)
    visited.append(node)

    for child in self.getChildren(node):
        if child not in visited:
            self.DFS_helper(child, visited)


def DFS(self, node):
    visited = []
    return self.DFS_helper(node, visited)

请注意，在上面的代码示例中，我执行的是 self.DFS_helper... 而不是 return 语句。为什么是这样？

现在，我试图确定图中的两个节点是否可达。这是我的尝试。

def _isReachable(self, nodeA, nodeB, visited, stack):
    if len(stack) == 0:
        return False

    if nodeA == nodeB:
        return True

    front = stack.pop(0)
    visited.add(front) # mark the node as visited

    for neighbor in nodeA.neighbors:
        if neighbor not in visited: # if it's not already been visited
            stack.append(neighbor)
            return self._isReachable(neighbor, nodeB, visited, stack)

# given a directed graph, returns true if there is a route from nodeA to nodeB
# Returns false otherwise
# this method essentially runs a DFS from nodeA to nodeB
def isReachable(self, nodeA, nodeB):
    if nodeA == None or nodeB == None:
        return False
    if nodeA == nodeB:
        return True

    stack = [nodeA]
    visited = set()
    return self._isReachable(nodeA, nodeB, visited, stack)

它不仅不起作用，而且我不太确定我理解调用递归函数和返回它的结果之间的区别。我已经尝试了两种方法都无济于事。在代码和概念上对我的任何帮助将不胜感激!

Answer 1

问题出在你的返回语句中:

return self._isReachable(neighbor, nodeB, visited, stack)

在这里，您在找到第一个 child 的结果后中断，而不是汇总所有 child 的结果。

看这个例子:

source: a
target: d

      a
    /   \
  /       \
 b          c
            |
            |
            d

现在，如果您在 (c,d) 之前通过 (a,b) 遍历图形，则此返回语句将意味着您不会探索 c 然后是 d，你会回答 d is not connected.

要解决，需要返回_isReachable(b,...) or _isReachable(c,...)

(当然，将其概括为每个节点有两个以上的 child )