Подходящий алгоритм для поиска всех петель транзитивного замыкания в графе?

Я хочу найти все циклы транзитивного замыкания на моем графике, имеющие следующие условия:

  1. если все узлы, присутствующие в идентифицированной петле, являются подмножеством другой идентифицированной петли, то мы будем рассматривать только надмножество.
  2. найти все различные петли.

ПРИМЕЧАНИЕ: читайте «петля» как -> цикл транзитивного замыкания (т.е. узлы в наборе транзитивного замыкания)


person roul ze    schedule 06.12.2011    source источник
comment
Судя по вашему описанию, вы ищете алгоритм для поиска сильно связанных компонентов.   -  person Sergey Kalinichenko    schedule 15.05.2012


Ответы (1)


Используйте алгоритм Floyd-Warshall только для транзитивной части, затем проверьте наличие рефлексивной части. петли, так как транзитивные петли в конце концов будут представлены как рефлексивные петли.

person belgther    schedule 06.12.2011