4

I am searching for an algorithm for finding every weakly connected component in a directed graph. I know for an undirected graph you can do this via a dfs but this obviously doenst work for an directed graph. I am saving my graph as an adjacents list. For example:

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

So A-B-C is a connected component an D-X

I am not searching for an algorithm for finding strongly connected components!!

4

2 回答 2

3

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

于 2016-03-18T18:29:24.047 回答
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)
于 2016-03-18T22:34:36.927 回答