用于有向图中的循环检测的多线程算法

Question

我正在寻找一种并发算法,它可以帮助我检测有向图中的周期.

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

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

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

(我希望上面说清楚.图中的边缘都是顶部的)

对于上述有向图,在并发执行期间可以执行以下操作.

(我假设的着色方案是白色 - 未访问,灰色 - 执行dfs未完成和黑色 - 完成执行和访问)

Dfs(B)由线程1,最终将E颜色为灰色并执行dfs(E)(导致F).在此之前,线程2执行dfs(C).它意识到E是灰色的并报告一个明显不是这种情况的循环.

我检查过Tarjan的算法也可以用于循环检测,但我不认为它的执行在多线程环境中是正确的.

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

谢谢.

Answer 1

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

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

如果该位已设置，则该项目的颜色为灰色。

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