如何跟踪在广度优先搜索的路径？

本文介绍了如何跟踪在广度优先搜索的路径？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

你如何跟踪的广度优先搜索的路径，例如，在下面的例子：

如果搜索键 11 ，返回最短列表中连接1至11。

[1，4，7，11]

解决方案

您应该看看en.wikipedia/wiki/Breadth-first_search第一。

下面是一个快速的实现，其中，我使用的列表的列表重新present的路径队列中。

＃图是在相邻的列表重新presentation 图= {         '1'：['2'，'3'，'4']，         '2'：['5'，'6']，         '5'：['9'，'10']，         '4'：['7'，'8']，         '7'：['11'，'12']         } 高清BFS（图，开始，结束）：     ＃保持路径的队列     队列= []     ＃推第一路径到队列     queue.append（[开始]）     而队列：         ＃从队列获取第一路径         PATH = queue.pop（0）         ＃获取从路径的最后一个节点         节点=路径[-1]         ＃路径发现         如果节点==结束：             返回路径         ＃枚举所有的相邻节点，构建一个新的路径，并推入队列         为在相邻的graph.get（节点，[]）：             new_path =列表（路径）             new_path.append（相邻）             queue.append（new_path） 打印BFS（曲线图中，'1'，'11'）

另一种方法是将保持从每个节点映射到其父，并且当检查ajacent节点，记录它的父。当搜索完成后，只需根据父映射回溯。

图= {         '1'：['2'，'3'，'4']，         '2'：['5'，'6']，         '5'：['9'，'10']，         '4'：['7'，'8']，         '7'：['11'，'12']         } 高清回溯（父母，开始，结束）：     路径= [结束]     而路径[-1] =启动！         path.append（父[路径[-1]]）     path.reverse（）     返回路径 高清BFS（图，开始，结束）：     父= {}     队列= []     queue.append（开始）     而队列：         节点= queue.pop（0）         如果节点==结束：             返回回溯（父母，开始，结束）         为在相邻的graph.get（节点，[]）：             家长[相邻] =节点＃＆LT;＆LT;＆LT;＆LT;＆LT;记录它的父             queue.append（相邻） 打印BFS（曲线图中，'1'，'11'）

C $ CS上面$是基于这样的假设，有没有循环

How do you trace the path of a Breadth-First Search, such that in the following example:

If searching for key 11, return the shortest list connecting 1 to 11.

[1, 4, 7, 11]

解决方案

You should have look at en.wikipedia/wiki/Breadth-first_search first.

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')

Another approach would be maintaining a mapping from each node to its parent, and when inspecting the ajacent 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, []): 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.