深度优先搜索返回的从图的一个顶点到另一个顶点的路径包含不必要的顶点

Question

在Kent D.Lee的教科书《Python的数据结构和算法》中，使用深度优先搜索存在一个问题。根据这本书，我必须：

Write a program to find a path between vertex 9 and 29 in the graph shown in Fig. 7.9. Be sure to print the path (i.e. the sequence of vertices) that must be traversed in the path between the two vertices.

代码如下：

def graphDFS(G, start, goal):
    def adjacent(current, edges):
        adj_list = []

        for e in edges:
            if current == e[0]:
                adj_list.append(e[1])

        return adj_list

    stack = []
    visited = set()
    path = []

    stack.append(start)

    while not len(stack) == 0:
        current = stack.pop()
        visited.add(current)
        path.append(current)

        if current == goal:
            return path
            # return True  # or return path to goal perhaps

        for v in adjacent(current, G[1]):
            if v not in visited:
                stack.append(v)

    return []

有向图的图像链接如下：(See Fig. 9 for the graph)

我目前拥有的路径是[9, 3, 2, 8, 13, 16, 17, 6, 24, 27, 29]。不过，当我最后检查结果时，整个过程都很好，除了那6条。我猜这与使用的堆栈有关。有人知道我的代码出了什么问题吗

谢谢D

Answer 1

解决这个问题的方法有很多。首先，您可以运行BFS而不是DFS，或者您可以使用不相交的并集（DSU）执行一些“手波浪”操作，以查找图形中两个顶点之间的路径