2つのノード間にルートが存在するかどうかを調べるための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文ではないことに注意してください。どうしてこれなの？

今、グラフの2つのノードに到達可能かどうかを判断しようとしています。ここに私の試みです。

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文である：

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

ここでは、あなたの代わりに、すべての子どもたちの結果を集約すると、最初の子の結果を発見した後断ちます。この例では

ルック：あなたが(c,d)前(a,b)を経由して、グラフを横断した場合

source: a 
target: d 

     a 
    / \ 
/  \ 
b   c 
      | 
      | 
      d 

さて、このreturn文は、あなたがc、その後dを探求するつもりはありません意味します、そしてあなたがdにお答えしますです接続されていません。

は、それを解決するために、あなたは返す必要が_isReachable(b,...) or _isReachable(c,...)

私はDFS_helper（自己、ノードは、訪問した）、DFS（自己 `信じる