如何在networkx中进行随机BFS遍历？

Question

我想以随机顺序在大图上实现 BFS 遍历算法（必须与普通 BFS 遍历一样快）。

这是我的代码片段：

def perform_random_bfs(self, g, source):
    visited = set()
    queue = [source]
    random_dfs_list = [source]
    visited.add(source)
    while len(queue):
        curr = queue.pop(0)
        childs = []
        for child in g.neighbors(curr):
            if child not in visited:
                visited.add(child)
                childs.append(child)
                queue.append(child)
        random.shuffle(childs)
        [random_dfs_list.append(child) for child in childs]
    return random_dfs_list

有什么加快速度的想法吗？我认为 random.shuffle 是瓶颈。

Answer 1

这取决于邻接信息的存储方式以及neighbors()方法如何访问它。

如果每个顶点都有一个邻接列表属性：

- LOOP over vertices
    - SHUFFLE vertex adjacency list
- PERFORM standard search

如果你有一个邻接矩阵并且 neighors() 查看列：

- SHUFFLE rows in adjacency matrix
- PERFORM standard search

邻接矩阵将是最快的。