大图形作为输入以查找所有路径

Question

我使用以下python代码来查找每两个节点之间的所有路径。这对小图形来说没有任何问题。

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)
for node3 in graph:
        for node4 in graph:
            few = bfs(graph, node3, node4)
            if not few == None:
                print ("{0} -> {1}".format(node3,node4))
                print (few)
                print ("n")

但是，对于一个大约有4K个节点和20K条边的大型图，我想找到每两个节点之间的所有路径。该程序会入侵并且不返回任何输出。

你能帮助我如何设置输入图，以及如何设置要添加到单独文件中的输出吗？

Answer 1

您的答案是，这可能无法完成，除了如果您的图是一个特殊的图，则该图中两个节点之间的路径数可能很大。请考虑以下情况：对于一个包含200个顶点和20K条边的完整图，存在198/2任意两个顶点之间的不同路径。如果图包含一个循环，则其中有无限路径。
你的图可能在两个顶点之间有如此多的路径，即使是超级计算机也无法在十年内计算出这个数字。