深度優先搜索，遞歸，For循環，並返回

我試圖實現DFS算法來確定在start節點和target節點之間是否存在路徑。這裏是我到目前爲止的代碼：深度優先搜索，遞歸，For循環，並返回

# Depth-first search 
def find_path2(s, t): 
    s.visited = True 

    if s.data == t.data: 
     return True 

    for node in s.neighbors: 
     if not node.visited: 
      return find_path2(graph, node, t) 


node_0 = Node(0) 
node_1 = Node(1) 
node_2 = Node(2) 
node_3 = Node(3) 
node_4 = Node(4) 
node_5 = Node(5) 
node_6 = Node(6) 

node_0.neighbors = [node_1] 
node_1.neighbors = [node_2] 
node_2.neighbors = [node_3, node_0] 
node_3.neighbors = [node_2] 
node_4.neighbros = [node_6] 
node_5.neighbros = [node_4] 
node_6.neighbors = [node_5] 

start = node_2 
target = node_0 


if find_path2(start, target): 
    print("There is a path between {} and {}".format(start.data, target.data)) 
else: 
    print("There is no path between {} and {}".format(start.data, target.data))

node_2既有Node_3上和node_0作爲鄰居，所以它應該打印在它們之間的路徑。我知道return語句在第一次執行期間正在退出for循環，因爲return語句退出函數，因此從不訪問node_0。

我的問題是，什麼是最優雅的方式去呢？謝謝！

來源

2017-02-13 YSA

是否如預期，或沒有此代碼的工作？維基百科上的DFS僞碼非常簡單，IMO。我認爲'find_path2（my_graph，node，t）'這個代碼錯誤'因爲'my_graph'不存在，只有2個參數需要傳遞 –

代碼中有很多錯誤，但是你描述的問題可能發生，只考慮'find_path2'中的其中一個鄰居。你可以嘗試用'return any（find_path2（node，t）for s.neighbors中的節點，如果不是node.visited）'替換'for'循環''。 – niemmi

'my_graph'是我忘記的舊參數，但是當我測試時，我刪除了它。 – YSA

你需要確保你只從環比鄰國返回，如果你發現你要尋找的節點：

def find_path2(s, t): 
    s.visited = True 

    if s.data == t.data: 
     return True 

    for node in s.neighbors: 
     if not node.visited: 
      if find_path2(node, t): 
       return True 
    return False

來源

2017-02-13 15:45:15

謝謝！這正是我所期待的。 – YSA

不客氣！ –

深度優先搜索，遞歸，For循環，並返回

回答

相關問題