Is there a way to run BFS in parallel in Python?

Question

I'm just learning about parallel computing and I was wondering if there's a way to run breath first search in parallel, such that every node's neighbors will simultaneously be traversed.
I have the following BFS code:

# 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]

If it is possible, will I need a separate GPU for each neighbor set? I'm not entirely sure how this works. e.g. in the example above, 1 is connected to [2,4]. Then, 2 is connected to 3, and 4 is connected to [9,7]. Will I need a one GPU for [2,4] and one for [3] , [9,7]?

question from:https://stackoverflow.com/questions/65599102/is-there-a-way-to-run-bfs-in-parallel-in-python

Answer 1

Waitting for answers