Ano*_*non 3 c++ algorithm search-engine code-search-engine graph-algorithm
我将我的图表表示为邻接列表.我想知道如何找到一个内部连接但没有边缘点的节点集群.有没有我可以使用的众所周知的算法？
对于egThis是我的图表.
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算法检测强连接组件.
找到这些组件后,将每个强连接组件压缩为一个节点(即,您通过单个节点表示整个组件).
在结果图中,您将查找没有传出边的节点.这些节点代表您感兴趣的组件.