@iliareznik
Начинающий

Можно ли единожды обойти все вершины связного неориентированного графа и вернуться в начальную вершину?

Какой алгоритм можно использовать для обхода всех вершин графа по одному разу с возвращением в начальную вершину.
Граф связный, неориентированный.
  • Вопрос задан
  • 296 просмотров
Пригласить эксперта
Ответы на вопрос 2
@antonksa
Можно ли обойти все вершины графа и вернуться в начальную?

Можно.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Судя по описанию, вам нужен Гамильтонов путь.

Эта задача NP-полна - следовательно, простого и быстрого алгоритма человечеству не известно. Можно делать полный перебор с отсечениями и эвристиками. Какие-нибудь методы имитации отжига или генетические алгоритмы могут работать быстрее, но это не точно и нужно долго и мучительно ковыряться, что бы оно заработало.
Ответ написан
Комментировать
Ваш ответ на вопрос

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

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