多线程与BFS，DFS搜索

多线程如何与此类似？

在使用BFS的多线程中，广度优先搜索，假设您正在运行10个线程，而对于源代码，则只有三个相邻的房间。

多线程如何在这种情况下工作？难道只有三个线程可以通过，因为如果您将队列的“推送”置于关键部分，那么发现的集合将在仅有3个线程后为空，这意味着只有三个线程能够通过那一点。多线程与BFS，DFS搜索

来源

2011-02-25 Jake

我不确定你想要完成什么，但也许检查线程池（http://en.wikipedia.org/wiki/Thread_pool_pattern）模式可能会有所帮助。使用线程池模式（取决于你如何分配工作）灯光工作负载肯定有可能会导致一些工作线程保持空闲状态。 – 2011-02-25 16:30:34

我还建议阅读生产者/消费者队列（http://en.wikipedia.org/wiki/Producer-consumer_problem），如果你不熟悉。 – 2011-02-25 16:35:50

你能提供更多背景知道你想要完成什么吗？您是否尝试实施多线程BFS/DFS搜索算法？或者你想对BFS/DFS顺序访问的顶点进行一些并行处理？ – 2011-02-25 16:39:46

查看Parallel Boost Graph Library。它具有BFS和DFS的并行实现。

来源

2011-02-25 19:46:28

当然，你应该根据相邻顶点的数量来分配线程。

如果一个线程发现所有相邻的顶点已经被其他线程处理或处理，它应该跳转到同步操作并在那里等待。

您可以使用共享变量来记录访问作业的线程数。将数字与线程第一行中相邻表的大小进行比较 - 如果大于大小，则表示所有相邻的顶点已交给系统中的其他线程 - 线程无关。

来源

2012-05-30 14:21:30 onesuper

多线程与BFS，DFS搜索

回答

相关问题