algorithm - 具有 BFS 的强连通分量

Question

如何在有向图中使用 BFS 找到强连通分量？

我知道使用DFS的Kosaraju算法。我想用BFS求。

Answer 1

一篇论文[ 1 ] 2014年来自宾夕法尼亚州立大学，提出了一种多步法，与前向后向算法相比减少了总工作量，并结合了几种并行SCC查找算法的优点。

他们对 BFS 使用了混合的自下而上方法 [ 2 ] 并大大减少了 BFS 期间所需的边缘检查总数。不同于 [ 2 ]，他们在运行自下而上的混合 BFS 时维护线程队列，而不是在关闭混合时从头开始显式重建队列，因为他们只需要访问数组来确定 SCC。