寻找图中互相连接但没有边指向外部的节点集群的算法

Question

4

我将我的图表示为邻接表。我想知道如何找到一个节点集群，这些节点在内部相互连接，但没有边指向外部。是否有任何众所周知的算法可供使用？

例如，这是我的图。

1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4

这里节点4和5内部相连，但没有任何外部边缘连接它们。这就是我的答案。同样，节点1、2、3虽然形成一个循环，但不符合作为外部边缘的标准，因为从节点3发出了一条外部边缘。

因此，这与在邻接表中查找循环并不相同。

可选阅读：（为什么我需要这个）我正在开发一个排名页面（搜索引擎）算法，像4和5这样的节点被称为排名汇。

- Anon

http://en.wikipedia.org/wiki/Strongly_connected_component - titus

@Anon：读完你的最后一行[可选阅读]后，我明白了。我已经删除了评论。 - amit

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phimuemue · Accepted Answer

你可以使用Kosaraju、Tarjan或Cheriyan-Mehldorn/Gabow算法检测强连通分量。

在找到这些分量后，你需要将每个强连通分量压缩为一个单独的节点（即用一个节点代表整个分量）。

在得到的图中，寻找没有出边的节点。这些节点表示你感兴趣的分量。