深度优先搜索、递归、For 循环和 Return

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