深度优先搜索，目标迭代

Question

我这里有一段代码，它是一个迭代DFS算法，现在它给出了它访问过的节点的输出。我想要一个只给我一个直接通往目标节点的路径的输出，我该怎么做？

第页。S由于我练习问题的一些限制，我不能用递归的方式来做这件事

graph = {"A": ["D", "F", "B"],
"B": ["C"],
"C": [],
"D": ["E"],
"E": ["G"],
"F": [],
"G": []}

def dfs_non_recursive(graph, source, goal):
if source is None or source not in graph:
return "Invalid input"
path = []
stack = [source]
while true:
s = stack.pop()
if s == goal:
path.append(s)
return path
if s not in path:
path.append(s)
if s not in graph:
# leaf node
continue
for neighbor in graph[s]:
stack.append(neighbor)
return path

DFS_path = dfs_non_recursive(graph, "A", "G")
print(DFS_path)

电流输出：['A', 'B', 'C', 'F', 'D', 'E', 'G']

所需输出：['A', 'D', 'E', 'G']

Answer 1

您必须使用字典来跟踪每个访问节点的父节点。然后，一旦到达目标节点，就使用字典回溯到源。

graph = {"A": ["D", "F", "B"],
"B": ["C"],
"C": [],
"D": ["E"],
"E": ["G"],
"F": [],
"G": []}

def dfs_non_recursive(graph, source, goal):
if source is None or source not in graph:
return "Invalid input"
path = []  # path to goal
parent = {} # stores parent of each node
stack = [source]
while len(stack) != 0:
s = stack.pop()
if s == goal:
path.append(goal)
while(s in parent.keys()):
path.append(parent[s])
s = parent[s]
return path[::-1]  # reverse of path
if s not in graph:
# leaf node
continue
for neighbor in graph[s]:
stack.append(neighbor)
parent[neighbor] = s
return path

DFS_path = dfs_non_recursive(graph, "A", "G")
print(DFS_path)