@inek18

Известен ли эффективный алгоритм поиска всех элементарных циклов в неориентированном графе?

Здравствуйте,
интересует вопрос:
имеется (известен ли) сейчас эффективный, реализуемый на каких-либо языках программирования алгоритм поиска всех элементарных (без повторения вершин) циклов в неориентированном графе, включая разумеется гамильтоновы, если они есть? Интересен факт существования такого алгоритма, реализация не обязательна, но при положительном ответе по возможности прошу писать о том, что реально где-то реализовывалось, а не о том, что "теоретически может быть реализовано" и привести описание алгоритма или ссылку на описание или источник. Также если известно, то указать размерность решаемой задачи или то, что она решена для общего случая (конечно для варианта с конечным временем).
Спасибо всем проявившим интерес!
  • Вопрос задан
  • 152 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Что вы подразумеваете под словом "эффективный"?

Проблема в том, что циклов в графе из n вершин может быть O(n!) (n-факториал): представьте клику - граф, где есть ребра между всеми парами вершин. Любое подмножество вершин, да еще и в любом порядке, задает элементарный цикл.

Обычно под словом "эффективный" подразумевают полиномиальный алгоритм. Такой алгоритм тут, очевидно, не существует (потому что надо перебрать экспоненциальное количество объектов).

Используйте обход в глубину без запоминания обойденных вершин. Такой полный перебор гарантированно найдет все циклы. Можно его ускорить, если предварительно разбить граф на двусвязные компоненты мостами и искать циклы внутри каждой компоненты отдельно.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы