c – 用于在图中找到内部连接的节点簇的算法,其中没有边缘向外指

发布时间：2020-12-16 09:37:09 所属栏目：百科来源：网络整理

导读：我将我的图表表示为邻接列表.我想知道如何找到一个内部连接但没有边缘点的节点集群.有没有我可以使用的众所周知的算法？例如,这是我的图表. 1----22----12----33----13----44----55----4 节点4和5在内部连接.然而,没有外界优势.这将是我的答案.类似地,节点1

我将我的图表表示为邻接列表.我想知道如何找到一个内部连接但没有边缘点的节点集群.有没有我可以使用的众所周知的算法？

例如,这是我的图表.

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

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

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

解决方法

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

找到这些组件后,将每个强连接组件压缩为一个节点(即,您通过单个节点表示整个组件).

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!