用于查找图中没有边缘指向外部的内部连接节点簇的算法
我将我的图表示为邻接列表。我想知道如何找到内部连接但没有向外的边缘点的节点集群。有没有我可以使用的众所周知的算法？
例如这是我的图表。
1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4
这里节点 4 和 5 是内部连接的。然而，这并没有带来任何外部优势。这就是我的答案。同样，节点 1、2、3 即使它们形成循环，也不符合标准，因为外部边缘源自节点 3。 所以它与在邻接表中查找循环不同。
可选阅读：（为什么我需要这个） 我正在研究排名页面（搜索引擎）算法，像 4 和 5 这样的节点称为排名下沉。
I am representing my graph as a adjacency list. I want to know how can I find a cluster of nodes which are internally connected but no edge points outwards from them. Is there any well known algorithm out there which I can use?
for e.g.This is my graph.
1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4
Here nodes 4 and 5 are internally connected. Yet no outside edge comes from this. This would be my answer. Similarly nodes 1,2,3 even though they form a cycle, do not fit the criteria as an outside edge emanates from node 3.
So it is not same as finding a cycle in a adjacency list.
Optional read: (why I need this)
I am working on a Ranking page (search engine) algorithm, nodes like 4 and 5 are called rank-sink.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以使用 强连接组件检测/wiki/Kosaraju%27s_algorithm" rel="noreferrer">Kosaraju, Tarjan 或 Cheriyan-Mehldorn/Gabow 算法。
找到这些组件后，您将每个强连接组件压缩到一个节点中（即用一个节点表示整个组件）。
在结果图中，您查找没有传出边的节点。这些节点代表您感兴趣的组件。
You could detect strongly connected components using Kosaraju, Tarjan or Cheriyan-Mehldorn/Gabow algorithm.
After finding these components, you compress each strongly connected components into one single node (i.e. you represent a whole component by a single node).
In the resulting graph, you look for nodes with no outgoing edges. These nodes represent the components you are interested in.