11

我正在寻找一种并发算法，它可以帮助我检测有向图中的循环。

我知道顺序算法使用带有着色的 dfs，但是我认为它在多线程环境中会失败。一个有向图的例子来说明它：

A->(B, C), B-> (D), D-> (E), C-> (E), E-> (F)

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

（我希望上面说清楚。图中的边都是从上到下的）

对于上述有向图，在并发执行过程中可以进行以下执行。

（我假设的配色方案是白色 - 未访问，灰色 - 未完成 dfs 执行和黑色 - 完成执行和访问）

线程 1 的 Dfs(B)，最终将 E 着色为灰色并执行 dfs(E)（导致 F）。在这完成之前，线程 2 执行 dfs(C)。它意识到 E 是灰色的，并报告了一个显然不是这种情况的循环。

我检查了 Tarjan 的算法也可以用于循环检测，但我再次认为它在多线程环境中的执行不会是正确的。

有人可以帮我解决这个问题吗？

谢谢。

4

3 回答 3

1

正如 Ira 所说，让每个线程使用自己的颜色。

但是，如果您有固定数量的线程，请为每种颜色使用位图。只要您的处理器支持原子位测试和设置（即 x86 上的 BTST），您就不需要锁定事件，因为每个线程都将测试和设置不同的位。

如果设置了该位，则该项目为灰色。

PS：如果您需要更多颜色，则可以使用更多位。

于 2012-05-22T09:03:55.377 回答
1

对于多线程循环检测，最好使用 Kahn 算法的变体（用于拓扑排序）而不是 DFS。这使用了以下事实：

1) 如果一个有向图是无环的，那么它至少有一个没有入边的顶点，并且至少有一个没有出边的顶点；

2）没有入边或出边的顶点不能参与循环；所以

3）如果您删除一个没有入边或出边的顶点，您将得到一个较小的有向图，其循环与原始图相同。

因此，要进行并行循环检测，您可以：

1）首先，使用并行 BFS 构建一个数据结构，跟踪每个顶点的入度和出度。

2）然后，并行地删除入度或出度为 0 的顶点。请注意，删除顶点将减少相邻节点的入度或出度。

3）当您没有要删除的顶点时，您将剩下所有涉及循环的顶点。如果没有，那么原始图是非循环的。

并行 BFS（步骤 1）和并行顶点移除（步骤 2）都可以通过并行工作队列轻松完成。在步骤 1 中，当您第一次看到一个顶点时，将一个任务添加到处理相邻顶点的队列中。在第 2 步中，当您将顶点的入度或出度减为 0 时，添加一个任务以将其从图中移除。

请注意，如果您只删除入度为 0 的节点或出度为 0 的节点，此算法同样有效，但并行性的机会会有所减少。

于 2016-07-11T14:10:58.487 回答
0

您应该很容易找到解决循环检测问题的分布式死锁检测算法。

我知道分布式并不完全是多线程，但你仍然应该在那里找到提示。

编辑：添加了一个受限的解决方案。

于 2012-05-22T09:59:55.973 回答