查找樹中兩個節點之間的（保證唯一）路徑

Question

我有一個（可能）簡單的圖遍歷問題。我是一個使用networkx作爲圖形數據結構的圖形新手。我的圖表總是這個樣子的：

   0 
     1    8 
    2  3  9  10 
4 5 6 7 11 12 13 14 

我需要從根節點返回給定節點的路徑（例如，path(0, 11)應該返回[0, 8, 9, 11]）。

我有一個沿其增長和收縮跟蹤什麼樣的路徑看起來像你遍歷樹，當目標節點被發現，最終被退回名單通過有效的解決方案：

def VisitNode(self, node, target, path): 
    path.append(node) 
    # Base case. If we found the target, then notify the stack that we're done. 
    if node == target: 
     return True 
    else: 
     # If we're at a leaf and it isn't the target, then pop the leaf off 
     # our path (backtrack) and notify the stack that we're still looking 
     if len(self.neighbors(node)) == 0: 
      path.pop() 
      return False 
     else: 
      # Sniff down the next available neighboring node 
      for i in self.neighbors_iter(node): 
       # If this next node is the target, then return the path 
       # we've constructed so far 
       if self.VisitNode(i, target, path): 
        return path 
      # If we've gotten this far without finding the target, 
      # then this whole branch is a dud. Backtrack 
      path.pop() 

我覺得我的骨頭裏沒有必要傳遞這個「路徑」列表......我應該能夠使用調用堆棧來跟蹤這些信息，但是我無法弄清楚......怎麼可能有人啓發我如何解決這個問題遞歸使用堆棧來跟蹤路徑？

Answer 1

您可以通過在失敗時返回None避免在路徑上傳遞，以及在成功時返回部分路徑。通過這種方式，您不必保留某種從根節點到當前節點的「breadcrumb trail」，但是如果您找到它，則只會構建從目標回到根的路徑。未經測試的代碼：

def VisitNode(self, node, target): 
    # Base case. If we found the target, return target in a list 
    if node == target: 
     return [node] 

    # If we're at a leaf and it isn't the target, return None 
    if len(self.neighbors(node)) == 0: 
     return None 

    # recursively iterate over children 
    for i in self.neighbors_iter(node): 
     tail = self.VisitNode(i, target) 
     if tail: # is not None 
      return [node] + tail # prepend node to path back from target 
    return None #none of the children contains target 

我不知道你正在使用的圖形庫，但我認爲，即使葉子含有neighbours_iter方法，這顯然不應該產生任何孩子一個葉子。在這種情況下，你可以離開了直接檢查葉子，使其成爲一個有點短：

def VisitNode(self, node, target): 
    # Base case. If we found the target, return target in a list 
    if node == target: 
     return [node] 
    # recursively iterate over children 
    for i in self.neighbors_iter(node): 
     tail = self.VisitNode(i, target) 
     if tail: # is not None 
      return [node] + tail # prepend node to path back from target 
    return None # leaf node or none of the child contains target 

我也刪除了一些else語句，因爲if你是從返回的真實部之中功能。這是常見的refactering pattern（一些老派人士不喜歡）。這消除了一些不必要的縮進。

Answer 2

你可以避免你的路徑參數在方法體內初始化路徑。如果方法在找到完整路徑之前返回，它可能會返回一個空列表。

但是你的問題也是關於在Depth-First-search實現中使用堆棧而不是列表，對吧？你在這裏得到一種風味：http://en.literateprograms.org/Depth-first_search_%28Python%29。

簡而言之，你

def depthFirstSearch(start, isGoal, result): 
    ###ensure we're not stuck in a cycle 

    result.append(start) 

    ###check if we've found the goal 
    ###expand each child node in order, returning if we find the goal 

    # No path was found 
    result.pop() 
    return False 

與

###<<expand each child node in order, returning if we find the goal>>= 
for v in start.successors: 
    if depthFirstSearch(v, isGoal, result): 
     return True 

和

###<<check if we've found the goal>>= 
if isGoal(start): 
    return True 

Answer 3

使用networkx直接：

all_simple_paths（G，源，目標，截留值=無）