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

 Здравствуйте,  

интересует вопрос:  

имеется (известен ли) сейчас эффективный, реализуемый на каких-либо языках программирования алгоритм поиска всех элементарных (без повторения вершин) циклов в неориентированном графе, включая разумеется гамильтоновы, если они есть? Интересен факт существования такого алгоритма, реализация не обязательна, но при положительном ответе по возможности прошу писать о том, что реально где-то реализовывалось, а не о том, что "теоретически может быть реализовано" и привести описание алгоритма или ссылку на описание или источник. Также если известно, то указать размерность решаемой задачи или то, что она решена для общего случая (конечно для варианта с конечным временем).  

Спасибо всем проявившим интерес! 

 Что вы подразумеваете под словом "эффективный"?  

  

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

  

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

  

Используйте обход в глубину без запоминания обойденных вершин. Такой полный перебор гарантированно найдет все циклы. Можно его ускорить, если предварительно разбить граф на двусвязные компоненты [мостами](https://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D1%81%D1%82_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)) и искать циклы внутри каждой компоненты отдельно.