用于查找有向图的每个弱连接组件的算法

Question

我正在寻找一种算法来查找有向图中的每个弱连通分量。我知道对于无向图，您可以通过 dfs 执行此操作，但这显然适用于有向图。我将我的图形保存为相邻列表。例如:

A -> B
B -> C
D -> X

所以 A-B-C 是 D-X 的连通分量

我不是在寻找用于查找强连通分量的算法!!

Answer 1

除非您的内存限制太严格，否则您可以保留第二个临时邻接表。在第二个邻接列表中，您将每条边放在 a->b 中，并将边放在相反的方向。 (即 b->a)然后，您可以在该邻接列表上使用 DFS 来查找连通分量。