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

Question

[Илья Резник]

Какой алгоритм можно использовать для обхода всех вершин графа по одному разу с возвращением в начальную вершину.
Граф связный, неориентированный.

Comments

[Армянское Радио]

Обходите граф любым известным способом (в ширину или в глубину), запоминайте пройденные вершины. Если зациклились - останавливаете движение. Если попали в начало - вы попали в начало.

В чем проблема-то?

[Илья Резник]

Армянское Радио, дело в том, что в каждой клетке нужно побывать не более одного раза

[Илья Резник]

Армянское Радио, а алгоритм в глубину предполагает, что программа вернется к клетке

[Армянское Радио]

Илья Резник, так запоминать надо - либо в проеденные вершины писать, что вы в них побывали, либо список хранить.

Answer 1

[antonksa]

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

Можно.

Comments

[Илья Резник]

Спасибо.
Если серьезно, то вы не занете граф, так что удачи.

[antonksa]

Илья Резник, Какой вопрос, такой и ответ.

[Илья Резник]

antonksa, вопрос находится ниже. Не засоряйте форум своим спамом.

[antonksa]

Илья Резник, Во-первых это не форум, во-вторых это вы засоряете его спамом и тупыми вопросами. Есть целые учебники по теории графов, в университете мне два семестра преподавали теорию графов, это большая, цельная и продуманная еще в 60-е дисциплина, в которой подробнейшим образом описаны алгоритмы обхода графов, направленных и нет, связных и нет. А вы вместо того, чтобы включить мозги и прочитать три страницы в гугле заполняете тостер под копирку одинаковыми вопросами "как включить компьютер", "как выключить компьютер", "как переключить компьютер".

Answer 2

[Wataru]

Судя по описанию, вам нужен Гамильтонов путь.

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