groostav03/14/2017, 10:03 PM
, can I use a
to avoid all the queue
elizarov03/15/2017, 6:47 AM
a new coroutine for each adjacent node. However, unless you are traversing a DAG, you also need to ensure that you visit each node at most once. That is, you get rid of a queue, but you still need to maintain a set of visited nodes and this set has to be shared between all the coroutines. At this point you have to choices: 1. Thread confinement. Using a single-threaded dispatcher you can just share this set between all the coroutines. It will work just like the classical single-threaded BFS, but I don’t really see that it is going simpler algo. It looks that there will be more code. 2. You can use something like
to maintain this set. Be careful to avoid “check&act” problem when you check if the node is not visited yet and launch a new coroutine (use an atomic
to launch a new coroutine). This way you can get a fully concurrent BFS, so that you can do some complex processing of each node (including async calls) and it will scale to lots of CPUs. This use-case might be worth it, IMHO.