Возможное дублирование:
Лучшее алгоритм обнаружения циклов в ориентированном графе
Я ищу алгоритм для поиска петель в ориентированном графе.
Мой график имеет метки только в узлах, а не на краях, и может стать довольно большим.
Результатом работы алгоритма должны быть циклы в виде набора списков, каждый список должен содержать метки узлов, участвующих в цикле, таким образом, первый и последний элементы в списке должны быть одинаковыми.
Графы, которые я использую, скорее всего, будут иметь только одну связную компоненту и не будут иметь сильносвязных компонентов. Ожидается, что количество циклов будет небольшим (мне еще предстоит это проверить).
Приветствуется любой хороший алгоритм именно этого или чего-то подобного.
Большое Вам спасибо.
PS: Если что-то неясно, не стесняйтесь спрашивать меня для более подробной информации, например, граф хранится (пока) как набор наборов ребер, от одного узла до нескольких узлов, обычно один, это не должно иметь значения, ПО МОЕМУ МНЕНИЮ.
