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

Question

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

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

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

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

Answer 1

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

Answer 2

一个非常简单的解决方案如下：
首先从给定的图创建一个无向图 - 只需制作一个副本并将每条边的反向添加到边集中。创建顶点集的副本，从任意顶点开始，然后 DFS 遍历包含该顶点的组件，从集合中删除所有遍历的节点并将它们添加到列表中。重复此操作直到列表为空。

在伪代码中：

bimap edges
edges.putAll(graph.edges())

set vertices = graph.vertices()

list result

while !vertices.isEmpty()
    list component

    vertex a = vertices.removeAny()
    dfsTraverse(a , v -> {
        vertices.remove(v)
        component.add(v)
    })

    result.add(component)

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

Algorithm for finding every weakly connected component of a directed graph

algorithm

graph

graph-algorithm

connected-components