python - 有没有办法在 Python 中并行运行 BFS？

Question

我只是在学习并行计算，我想知道是否有一种方法可以并行运行呼吸优先搜索，这样每个节点的邻居都会同时被遍历。
我有以下 BFS 代码：

# BFS
import collections

def breadth_first_search(graph, root): 
    visited, queue = set(), collections.deque([root])
    while queue: 
        vertex = queue.popleft()
        yield vertex
        visited.add(vertex)
        queue.extend(n for n in graph[vertex] if n not in visited)


graph = {1: [2, 4], 2: [3], 3: [8], 4: [9, 7], 5: [9], 6: [5], 7: [9], 8: [5], 9: []}
list(breadth_first_search(graph, 1))
#[1, 2, 4, 3, 9, 7, 8, 5]

如果可能的话，我是否需要为每个邻居集使用单独的 GPU？我不完全确定这是如何工作的。例如，在上面的示例中，1连接到[2,4]. 然后，2连接到3，并且4连接到[9,7]。我需要一个 GPU[2,4]和一个 GPU[3]吗[9,7]？

标签： pythonparallel-processingbreadth-first-search