Python 在寻路时卡住

我有一个脚本，它使用邻接图和 BFS 算法来查找两点之间的路径。该图有大约 10,000 个顶点，脚本设置如下:

graph = {... 
         '9660': ['9661', '9662', '9659'], 
         '9661': ['9654', '9660'], 
         '9662': ['9660', '9663'], 
         '9663': ['9664', '9662'], 
         '9664': ['9665', '9663'], 
                              ...} 
 
 
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, '50', '8659') 

因为这个算法适用于小的邻接图，我猜 python 只需要很长时间来处理这个大小的图。我的目标是找到最短路径，但如果我什至找不到一条路径，那目前是不可能的。是否有使用大型邻接图处理路径查找的 python 解决方案？如果是这样，我可以举个例子吗？

请您参考如下方法:

您没有跟踪访问过的节点，如果您的图不是有向无环图，这可能会导致大量时间浪费。例如，如果您的图表是

{'A': ['B', 'C', 'D', 'E'], 
 'B': ['A', 'C', 'D'], 
 'C': ['A', 'B', 'D'], 
 'D': ['A', 'B', 'C'], 
 'E': ['F'], 
 'F': ['G'], 
 'G': ['H'], 
 ... 
 'W': ['X'], 
 'X': ['Y'], 
 'Y': ['Z']} 

使用您的算法调用 bfs(graph, 'A', 'Z') 会在最终到达 Z 之前不必要地循环“A”、“B”、“C”和“D”。而如果您跟踪访问过的节点，则只需将“A”、“B”、“C”和“D”的邻居添加到队列中一次。

def bfs(graph, start, end): 
    # maintain a queue of paths 
    queue = [] 
 
    # push the first path into the queue 
    queue.append([start]) 
 
    # already visited nodes 
    visited = set() 
 
    while queue: 
        # get the first path from the queue 
        path = queue.pop(0) 
 
        # get the last node from the path 
        node = path[-1] 
 
        # if node has already been visited 
        if node in visited: 
            continue 
 
        # path found 
        if node == end: 
            return path 
        # enumerate all adjacent nodes, construct a new path and push it into the queue 
        else: 
            for adjacent in graph.get(node, []): 
                # add the path only if it's end node hasn't already been visited 
                if adjacent not in visited 
                    new_path = list(path) 
                    new_path.append(adjacent) 
                    queue.append(new_path) 
 
            # add node to visited set 
            visited.add(node) 

使用这个版本的算法和字母图，队列和访问集在整个算法的 while 循环顶部看起来像这样:

queue = [ ['A'] ] 
visited = {} 
 
queue = [ ['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'] ] 
visited = {'A'} 
 
queue = [ ['A', 'C'], ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], 
          ['A', 'B', 'D'] ] 
visited = {'A', 'B'} 
 
queue = [ ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], 
          ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C'} 
 
queue = [ ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C', 'D'} 
 
queue = [ ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 
 
queue = [ ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 
 
queue = [ ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 
 
queue = [ ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 
 
queue = [ ['A', 'E', 'F', 'G'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F'} 
 
queue = [ ['A', 'E', 'F', 'G', 'H'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'} 
 
... 
... 
 
queue = [ ['A', 'E', 'F', 'G', 'H', ..., 'X', 'Y', 'Z'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G', ..., 'X', 'Y'} 
 
# at this point the algorithm will pop off the path, 
# see that it reaches the goal, and return 

这比添加像 ['A', 'B', 'A', 'B', 'A', 'B', ...] 这样的工作要少得多。