如何跟踪广度优先搜索的路径,例如在以下示例中:
How do you trace the path of a Breadth-First Search, such that in the following example:
如果搜索键11,则返回连接1到11的最短列表.
If searching for key 11, return the shortest list connecting 1 to 11.
[1, 4, 7, 11] 推荐答案你应该看看 en.wikipedia/wiki/Breadth-first_search 首先.
下面是一个快速实现,其中我使用了一个列表列表来表示路径队列.
Below is a quick implementation, in which I used a list of list to represent the queue of paths.
# 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']
另一种方法是维护从每个节点到其父节点的映射,并在检查相邻节点时记录其父节点.搜索完成后,只需根据父映射回溯即可.
Another approach would be maintaining a mapping from each node to its parent, and when inspecting the adjacent node, record its parent. When the search is done, simply backtrace according the parent mapping.
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')以上代码基于没有循环的假设.
The above codes are based on the assumption that there's no cycles.
更多推荐
如何在广度优先搜索中跟踪路径?
发布评论