这似乎是一个有趣的问题,所以我试着解决它。这是我的尝试。你没有说你的图形格式是什么,所以我猜测它是像下面这样的字典格式:
example_graph = {0:[1,2], 1:[0,3,4], 3:[1], 4:[1], 2:[0,5,6], 5:[2], 6:[2]}
代码运行通过当前活动顶点的列表,从指定的起始和目标顶点开始,并通过{顶点:列表}的字典记住了如何通过它们。如果一个活动顶点发现自己紧邻另一个从另一端开始的活动顶点,它将合并列表并返回结果,否则它将扩展所有路径并继续运行。
def bi_directional_search(graph, start, goal):
if start == goal:
return [start]
active_vertices_path_dict = {start: [start], goal: [goal]}
inactive_vertices = set()
while len(active_vertices_path_dict) > 0:
active_vertices = list(active_vertices_path_dict.keys())
for vertex in active_vertices:
current_path = active_vertices_path_dict[vertex]
origin = current_path[0]
current_neighbours = set(graph[vertex]) - inactive_vertices
if len(current_neighbours.intersection(active_vertices)) > 0:
for meeting_vertex in current_neighbours.intersection(active_vertices):
if origin != active_vertices_path_dict[meeting_vertex][0]:
active_vertices_path_dict[meeting_vertex].reverse()
return active_vertices_path_dict[vertex] + active_vertices_path_dict[meeting_vertex]
if len(set(current_neighbours) - inactive_vertices - set(active_vertices)) == 0:
active_vertices_path_dict.pop(vertex, None)
inactive_vertices.add(vertex)
else:
for neighbour_vertex in current_neighbours - inactive_vertices - set(active_vertices):
active_vertices_path_dict[neighbour_vertex] = current_path + [neighbour_vertex]
active_vertices.append(neighbour_vertex)
active_vertices_path_dict.pop(vertex, None)
inactive_vertices.add(vertex)
return None