Алгоритм нахождения внутри связного кластера узлов в графе, из которого нет ребер, направленных наружу

Question

Я представляю свой график в виде списка смежности.Я хочу знать, как я могу найти кластер узлов, которые внутренне связаны, но без краевых точек от них.Есть ли какой-нибудь известный алгоритм, который я могу использовать?

для примера. Это мой график.

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

Здесь узлы 4 и 5 связаны между собой.И все же никакой внешний край не исходит из этого.Это был бы мой ответ.Точно так же узлы 1, 2, 3, даже если они образуют цикл, не соответствуют критериям, поскольку внешний край исходит от узла 3. Таким образом, это не то же самое, что нахождение цикла в списке смежности.

Необязательное чтение: (зачем мне это) Я работаю над алгоритмом страницы ранжирования (поисковой системы), такие узлы, как 4 и 5, называются ранжирование.

Answer 1

Вы можете обнаружить сильно связанные компоненты , используя Косараджу , Тарьяна или Чериан-Мелдорн / Габов алгоритм.

Найдя эти компоненты, вы сжимаете все сильно связанные компоненты в один узел (т.е. вы представляете целый компонент одним узлом).

В полученном графе вы ищете узлы без исходящих ребер.Эти узлы представляют интересующие вас компоненты.