tgoop.com/the_algorithms/4669
Last Update:
Гамильтонов цикл
Гамильтонов цикл — это цикл в графе, который посещает каждый узел ровно один раз и возвращается в начальный узел.
Алгоритм:
1. Начните с любого узла, отметьте его как посещенный и добавьте его в путь.
2. Если все узлы посещены и текущий узел имеет ребро к начальному узлу, верните путь как гамильтонов цикл.
3. Если не все узлы посещены, рекурсивно исследуйте непосещенных соседей. Для каждого непосещенного:
а. Отметить соседа как посещенного.
б. Добавьте соседа в путь.
в. Рекурсивно исследуйте этот новый путь.
4. Если рекурсивное исследование не приводит к гамильтонову циклу, вернитесь назад, удалив последний узел из пути и пометив его как непосещенный.
5. Продолжите процесс, выбрав другого непосещенного соседа текущего узла и исследовав его.
6. Если все соседи исследованы и ни один из них не ведет к гамильтонову циклу, вернитесь дальше, удалив текущий узел из пути и пометив его как непосещенный.
Сложность: O(N!), где N — количество вершин.
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4669