Я представляю свой график как список смежности. Я хочу знать, как я могу найти кластер узлов, которые связаны внутри, но не имеют внешних точек от них. Есть ли какой-нибудь известный алгоритм, который я могу использовать?
например, это мой график.
1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4
Здесь узлы 4 и 5 внутренне связаны. Тем не менее, из этого не исходит никакого внешнего края. Это будет мой ответ. Точно так же узлы 1, 2, 3, даже если они образуют цикл, не соответствуют критериям, поскольку внешнее ребро исходит из узла 3. Таким образом, это не то же самое, что найти цикл в списке смежности.
Дополнительное чтение: (зачем мне это нужно) Я работаю над алгоритмом страницы ранжирования (поисковая система), такие узлы, как 4 и 5, называются rank-sink.
