Поиск по глубине, рекурсия, для циклов и возврат

Question

Я пытаюсь реализовать алгоритм DFS, чтобы выяснить, существует ли путь между узлом start и узлом target. Вот код, который я до сих пор:

# 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.

Мой вопрос в том, что является самым элегантным способом для этого? Спасибо!

Answer 1

Вы должны убедиться, что вы только вернуться из цикла над соседями, если вы нашли узел, который вы ищете:

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