带有目标迭代的深度优先搜索

Question

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

P.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)

Answer 2

使用DFS时，

stack

（顺便说一句，我更喜欢将其命名为

to_visit

）准确包含从根到当前节点的路径。因此，当当前节点是目标节点时，你只需要停止

def dfs_non_recursive(graph, source, goal):
    if source is None or source not in graph:
        return "Invalid input"

    stack = [source]
    visited = set()
    found = False
    while not found:
        cur = stack[-1] if stack else None  # peek
        if cur is None:
            # finished DFS but no path found, just break to return the
            # empty stack to reflect that.
            break

        for each in graph[cur]:
            if each in visited:
                pass
            else:
                visited.add(each)
                stack.append(each)
                if each == goal:
                    found = True
                break # add one at a time because we are DFS-ing

        if stack[-1] == cur: # has visited all children, pop up this one
            stack.pop()

    return stack