Algorithm for finding internally connected cluster of nodes within a graph from which no edge points outwards

StackOverflow https://stackoverflow.com/questions/7416574

Вопрос

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.

Нет правильного решения

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top