multithreading with BFS, DFS searches

How does multithreading with like this?

In multithreading with BFS, breadth first search, let's say you are running 10 threads and for the source there are only three adjacent rooms.

How will multithreading work in this case? Won't there only be three threads that can get through because if you put the "push" of the queue in the critical section, then the discovered set will be empty after only 3 threads, meaning only three threads will be able to get past th开发者_如何学Cat point.

Check out the Parallel Boost Graph Library. It has parallel implementations for BFS and DFS.

Sure, You should assign the threads according to the number of adjacent vertices.

If a thread find all the adjacent vertices have been processed or processing by other threads, it should jump to synchronize operation and wait there.

You can use a shared variable to record how many threads are doing the visiting job. Compare the number to the size of adjacent table at the first line of a thread - if it is greater than the size, it means all the adjacent vertices has been hand to other threads in the system - the thread has nothing to do.