如何在广度优先search中追踪path？
如何跟踪广度优先search的path，以便在以下示例中：
如果search键11 ，则返回连接1到11的最短列表。
[1, 4, 7, 11]
你应该先看看http://en.wikipedia.org/wiki/Breadth-first_search 。
下面是一个快速实现，其中我使用列表来表示path的队列。
# 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')
另一种方法是维护从每个节点到其父节点的映射，并在检查相邻节点时logging其父节点。 search完成后，根据父映射进行回溯。
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')
上面的代码是基于没有周期的假设。
我非常喜欢乔的第一个答案！ 这里唯一缺less的是将顶点标记为已访问。
为什么我们需要这样做？
让我们设想从节点11连接另一个节点号13.现在我们的目标是find节点13。
稍微运行一下之后，队列将如下所示：
[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]
请注意，最后有两个节点号为10的path。
这意味着来自节点号10的path将被检查两次。 在这种情况下，它看起来并不坏，因为节点号码10没有任何孩子..但它可能是非常糟糕的（即使在这里，我们将无故检查该节点两次）
节点号13不在这些path中，所以程序在到达第二个节点号为10的path之前不会返回。我们将重新检查它。
我们所缺less的是一组标记访问节点，而不是再次检查它们。
这是修改后的乔的代码：
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)
该scheme的输出将是：
[1, 4, 7, 11, 13]
没有unneccecery rechecks ..
我想我会尝试代码这个有趣的：
graph = { '1': ['2', '3', '4'], '2': ['5', '6'], '5': ['9', '10'], '4': ['7', '8'], '7': ['11', '12'] } def bfs(graph, forefront, end): # assumes no cycles next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]] for node,path in next_forefront: if node==end: return path else: return bfs(graph,next_forefront,end) print bfs(graph,[('1','1')],'11') # >>> # 1, 4, 7, 11
如果你想循环，你可以添加这个：
for i, j in for_front: # allow cycles, add this code if i in graph: del graph[i]
我喜欢乔先回答和Or的加法。 为了less一点处理，我想添加到Or的答案。
在Or的跟踪访问节点的答案是伟大的。 我们也可以让程序尽快退出。 在for循环中的某一点， current_neighbour将不得不end ，一旦发生，find最短path并返回程序。
我会修改如下的方法，密切关注for循环
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) #No need to visit other neighbour. Return at once if current_neighbour == end return new_path; # Mark the vertex as visited visited.add(vertex) print bfs(graph, 1, 13)
输出和其他一切将是相同的。 但是，代码将花费更less的时间来处理。 这在更大的图表上特别有用。 我希望这将有助于未来的人。
