4

我将我的图表示为邻接列表。我想知道如何找到内部连接但没有边缘点从它们向外的节点集群。有没有我可以使用的众所周知的算法?

例如这是我的图表。

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

这里节点 4 和 5 是内部连接的。然而,没有外部优势来自于此。这将是我的答案。同样,节点 1,2,3 即使它们形成一个循环,也不符合标准,因为外部边缘来自节点 3。因此它与在邻接列表中查找循环不同。

可选阅读:(为什么我需要这个)我正在研究排名页面(搜索引擎)算法,像 4 和 5 这样的节点被称为 rank-sink。

4

1 回答 1

7

您可以使用KosarajuTarjanCheriyan-Mehldorn/Gabow算法检测强连通分量。

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

在结果图中,您查找没有出边的节点。这些节点代表您感兴趣的组件。

于 2011-09-14T12:54:36.250 回答