如何在广度优先搜索中追踪路径？

Question

如何追踪广度优先搜索的路径呢？在下面这个例子中：

如果我们要找的关键字是 11，那么就要返回从1到11的最短路径列表。

[1, 4, 7, 11]

Answer 1

我非常喜欢qiao的第一个回答！
唯一缺少的就是要把访问过的节点标记一下。

为什么我们需要这样做呢？
假设有一个节点13是从节点11连接过来的。现在我们的目标是找到节点13。
经过一段时间的运行，队列会变成这样：

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

注意到有两个路径的末尾都是节点10。
这意味着从节点10出发的路径会被检查两次。在这种情况下，看起来还好，因为节点10没有子节点……但如果有子节点的话，那就会很糟糕（即使在这里，我们也会无缘无故地检查这个节点两次……）
节点13不在这些路径中，所以程序在到达第二条以节点10为末尾的路径之前是不会返回的……而我们还会重新检查它。

我们缺少的就是一个集合，用来标记已经访问过的节点，这样就不会再检查它们了。
这是qiao修改后的代码：

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

程序的输出将是：

[1, 4, 7, 11, 13]

这样就避免了不必要的重复检查……

Answer 2

这段代码非常简单。每当你找到一个节点时，就把路径加到后面。

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))

Answer 3

你可以先看看这个链接：http://en.wikipedia.org/wiki/Breadth-first_search。

下面是一个简单的实现，我用一个列表的列表来表示路径的队列。

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a 
        # new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

这个代码的输出是：['1', '4', '7', '11']

另一种方法是为每个节点维护一个到它父节点的映射，当检查相邻节点时，记录下它的父节点。搜索完成后，只需根据父节点的映射进行回溯。

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path
        

def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

上面的代码是基于没有循环的假设。

如何在广度优先搜索中追踪路径？

7 个回答

撰写回答