在没有向外的边点的图中寻找内部连通的节点簇的算法

Question

我将我的图表示为邻接表。我想知道如何才能找到一组内部连接但没有向外的边缘点的节点。有没有什么我可以使用的众所周知的算法？

因为e.g.This是我的图表。

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

这里，节点4和5是内部连接的。然而，没有任何外部优势来自于此。这就是我的答案。类似地，节点1、2、3即使形成一个循环，也不符合标准，因为外边是从节点3发出的。因此，这与在邻接表中查找循环不同。

可选阅读：(为什么我需要这个)我正在研究一个排名页面(搜索引擎)算法，像4和5这样的节点被称为排名接收器。

Answer 1

您可以使用Kosaraju、Tarjan或Cheriyan-Mehldorn/Gabow算法来检测strongly connected components。

找到这些组件后，将每个强连接组件压缩到一个节点中(即用一个节点表示整个组件)。

在生成的图中，您将查找没有传出边的节点。这些节点表示您感兴趣的组件。