如何在广度优先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的时间来处理。 这在更大的图表上特别有用。 我希望这将有助于未来的人。