问题描述
我正在尝试实现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。
我的问题是，最优雅的方法是什么？ 谢谢！
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