python - 通过某种内存提高 BFS 性能

Question

我有这个问题，我正在尝试构建一种算法，该算法将查找图中一个顶点到其他顶点的距离。

让我们用一个非常简单的例子来说明我的网络是这样的:

network = [[0,1,2],[2,3,4],[4,5,6],[6,7]]

我创建了一个 BFS 代码，它应该找到从指定源到其他图的顶点的路径长度

from itertools import chain
import numpy as np

n = 8
graph = {}

for i in range(0, n):
    graph[i] = []

for communes in communities2:
    for vertice in communes:
        work = communes.copy()
        work.remove(vertice)
        graph[vertice].append(work)

for k, v in graph.items():

    graph[k] = list(chain(*v))

def bsf3(graph, s):
    matrix = np.zeros([n,n])
    dist = {}
    visited = []
    queue = [s]
    dist[s] = 0
    visited.append(s)
    matrix[s][s] = 0

    while queue:

        v = queue.pop(0)
        for neighbour in graph[v]:

            if neighbour in visited:
                pass
            else:

                matrix[s][neighbour] = matrix[s][v] + 1


                queue.append(neighbour)
                visited.append(neighbour)



    return matrix

bsf3(graph,2)

首先，我正在创建图表(字典)，然后使用该函数查找距离。

我担心的是，这种方法不适用于更大的网络(假设那里有 1000 人)。我正在考虑的是使用某种内存(实际上这就是我制作矩阵而不是列表的原因)。这个想法是，当算法计算从 0 到 3 的路径(它已经做了什么)时，它应该以矩阵 [1][3] = 1 等的方式跟踪另一条路线。

所以我会使用像 bsf3(graph, 1) 这样的函数，它不会从头开始计算所有内容，但能够从矩阵中访问一些值。

提前致谢!

Answer 1

知道这一点并不能完全回答您的问题，但这是您可以尝试的另一种方法。

在网络中，网络中的每个节点都有一个路由表。您只需保存网络内所有节点的列表以及您必须去的节点。 D节点路由表示例

A -> B
B -> B
C -> E
D -> D
E -> E

您需要在每个节点上运行 BFS 来构建所有路由表，这将花费 O(|V|*(|V|+|E|)。空间复杂度是二次的，但您必须检查所有可能的路径。

当您创建所有这些信息时，您可以简单地从一个节点开始并在表中搜索您的目标节点并找到下一个节点。这将提供更好的时间复杂度(如果您为表使用正确的数据结构)。