Изменения

Перейти к: навигация, поиск

Гамильтоновы графы

12 байт добавлено, 00:09, 10 января 2016
Алгоритм нахождения гамильтонова цикла
==== Алгоритм нахождения гамильтонова цикла ====
Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла.
В массиве <tex>d[i][mask] </tex> мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex> true</tex>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
==== Алгоритм нахождения гамильтового пути ====
Анонимный участник

Навигация