how to implement multithreaded Breadth-first search in java?

Question

I've done the breadth-first search in a normal way. now I'm trying to do it in a multithreaded way. i have one queue which is shared between the threads. i use synchronize(LockObject) when i remove a node from the queue ( FIFI queue ) so what I'm trying to do is that. when i thread finds a solution all the other threads will stop immediately.

Answer 1

i assume you are traversing a tree for your BFS.

create a thread pool. for each unexplored children in the node, retrieve a thread from the thread pool (perhaps using a Semaphore). mark the child node as 'explored' and explore the node's children in a BFS manner. when you have found a solution or done exploring all the nodes, release the semaphore.

^ i've never done this before so i might have missed out something.