Графы. Гамильтонов Цикл в C++.

Гамильтонов Цикл в C++

Есть интересная наука, которая называется Теория графов. В программировании можно встречать много задач, которые на теорию графов опираются. Я не буду переписывать о графах из других источников, а опишу немного по-своему. Здесь будет описан именно Гамильтонов цикл. Это первое мое знакомство с материалами из теории графов, поэтому здесь простой и не глубокий материал.

Чтобы объяснить, что такое Гамильтонов цикл, я приведу 2 визуальных примера. Очень простой и чуть-чуть посложнее.
Советую перерисовать дом с номерами на лист бумаги, удобнее будет смотреть позже.
Гамильтонов цикл в C++ Это самый простой пример. Слева нарисован рисунок. Справа у рисунка обозначены некоторые точки. Если представить, что линии — это дороги, а точки — пункты назначения, то существует множество маршрутов между этими точками. Предлагаю сыграть в простую игру.

  • Вы командир снайперов. У вас есть 5 снайперов, которых надо расставить по 5 пунктам. Ваши начальники жестоко над вами пошутили и дали вам 5 снайперов дальтоников. Задача каждого снайпера стрелять в любого, кто остановится или свернет в его точке. Т.е. вы двигаетесь по маршруту, оставляете в каждой точке снайпера. Если вы останавливаетесь или сворачиваете в точке, где снайпер есть, то вся ваша оставшаяся команда умирает под обстрелом.

Надеюсь смысл понятен. Вы должны вернутся на базу один и целым. База — это точка выхода. Откуда вышли, над туда прийти.

 

Вот пример. Поможет понять правило игры.
Старт точка 4:
4—>3—>1—>2—>4 Снайпер с точки 4 вас убил за то, что у вас снайпер остался. Ведь вы вернулись на базу не выполнив приказ.
Если делать проход по 3-4, то дальше в одной из точек будете убиты.
Но можно пройти 4—>5—>3—>1—>2—>4, снайперы на месте, вы на базе. Совсем не обязательно по всем дорогам шататься, главное посещение нужных точек и не попадаться на глаза оставленным снайперам.
Если бы между 2 и 4 был пункт 6, то можно было двигаться 2—>4—6, дальше снайпер. Если бы в 6 стоял снайпер, а вы шли 2—>4, то снайпер 6 вас не трогает, вы не остановились и прошли прямо.

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

А сейчас поясню как оно программируется. Для начала я буду использовать матрицу смежности.

  • Матрица смежности — Это квадратная матрица, элементы которой показывают, смежны ли вершины друг с другом. Если элемент матрицы x[i,j]=0, то вершины i и j не смежны, если x[i,j]=1 — то смежны (смежными называются вершины, которые соединяются ребром (дугой) графа)

Чтобы было понятнее, попытаюсь объяснить. Давайте смотреть на нумерованный рисунок и отталкиваться от нумерованных узлов по порядку. (удобнее если вы все-таки срисовали)
1) 1 соединен с 2 и 3 (значит 1 смежно с 2 и 3)
2) 2 соединен с 4 и 1
3) 3 соединен с 1, 4 и 5
4) 4 соединен с 2, 3 и 5
5) 5 соединен с 3 и 4

Из этой информации нужно создавать матрицу. Сначала просто пронумеруем поле для матрицы

     1    2    3    4    5
1
2
3
4
5

Отсчет у нас от единицы. Можно делать от нуля, но мне оказалось проще так. Теперь постепенно заполняем матрицу нулями и единицами. Смотрим на информацию выше (там где про соединения) и расставляем по матрице значения.
1) 1 соединен с 2 и 3 (значит 1 смежно с 2 и 3)
———————
     1    2    3    4    5
1   0   1    1    0    0
2
3
4
5
———————
Видите связь? Внимательно присмотритесь. Слева у нас номер узла, сверху номер другого узла. Если узлы соединены, то ставим 1, если нет, то 0. Дальше заполняем матрицу аналогично. Итоговая матрица по рисунку получается
———————
     1    2    3    4    5
1   0   1    1    0    0
2   1   0    0    1    0
3   1   0    0    1    1
4   0   1    1    0    1
5   0   0    1    1    0
———————
Я очень надеюсь, что смог объяснить как составляется матрица смежности, потому что эту матрицу смежности мы будем подставлять в программу.

Исходник Гамильтонова цикла

Программа есть. Смотрим результат.
3—>1—>4—>2—>5—>3
Программа показала нам нужный маршрут нашей простецкой игры.

Давайте немного усложним сам рисунок для теста программы. Как я предлагал выше, попробуйте сами найти нужный маршрут, согласно нашим правилам. Думаю это может вызывать некоторые затруднения. Найти без помощи компа.
Гамильтонов Цикл в C++

Даже если пробовали, но не особо получается, то ведь мы теперь знаем о существовании Гамильтонова цикла и получили о Гамильтоновом цикле первое представление. Даже знаем, что этот Гамильтоновый цикл можно заложить в исходник программы и знаем как. Единственное неудобство — это составление и подставление матрицы смежности в программу. Здесь 13*13 элементов в матрице, поэтому требуется быть очень внимательным.

Я не буду повторять исходник. Там достаточно поменять N=13 и поменять матрицу на новую. Имеет смысл понять как составляется матрица. Выше я описал насколько смог, чтоб было проще разбираться, здесь показываю итоговую для текущего рисунка
0,1,0,0,0,1,0,0,0,0,0,0,0,
1,0,0,1,0,0,0,1,0,0,0,0,0,
0,0,0,1,1,0,1,0,1,0,0,0,0,
0,1,1,0,1,0,0,1,0,0,0,0,0,
0,0,1,1,0,0,0,0,0,1,0,0,0,
1,0,0,0,0,0,1,1,0,0,0,0,0,
0,0,1,0,0,1,0,1,1,0,0,0,0,
0,1,0,1,0,1,1,0,0,0,0,0,0,
0,0,1,0,0,0,1,0,0,1,1,0,0,
0,0,0,0,1,0,0,0,1,0,1,1,0,
0,0,0,0,0,0,0,0,1,1,0,0,1,
0,0,0,0,1,0,0,0,0,1,0,0,1,
0,0,0,0,0,0,0,0,0,0,1,1,0

Вы можете сами пробовать свои силы в составлении матрицы. Сверить очень просто — подставить мою в программу и посмотреть результат, потом вашу и посмотреть результат. А если вы поняли правило предложенной игры, то даже сверять результаты двух запусков программы не надо, достаточно визуального прохода по точкам. Можно на листе бумаги закрашивать точки со снайпером.

P.S. Такое вот обобщенное представление Гамильтонова цикла из теории графов в C++ получилось создать.

18 комментариев на «“Графы. Гамильтонов Цикл в C++.”»

  1. Влад:

    Большое Спасибо!!!!

  2. Евгений:

    Опиши Гамильтонов Путь

    Автор сайта отвечает:
    Сейчас не смогу. Я в этом не понимаю и неизвестно еще смогу ли понять вообще.

  3. Данила:

    Хороший алгоритм)) У меня немного другой и я с помощью него сделал вот такую прогу http://yadi.sk/d/D7AIMv7P2_zYO это мой курсач))

  4. Роза:

    Автор! Вы спасаете тонны студентов ежегодно! Спасибо большое за открытые исходники) две группы излучают добро на вашу душу)

  5. Сергей:

    Спасибо за программу!
    Можете пояснить для чего нужны переменные q1 и k? и что они выполняют

    Автор сайта отвечает:
    Переменная k – это параметр, который принимает функция. Стартовая точка маршрута.
    q1 не помню.

  6. Сергей:

    в 42 строке c[v]=-1
    откуда у нас появилось значение -1?

    Автор сайта отвечает:

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

    чтобы понять нужно врубаться в ход выполнения рекурсии.
     
    и это не обязательно -1, можно – 1000, только в 38 сравнивать уже с -1000 нужно будет.

  7. mamuka:

    a vi mojete obiasnic sto int gamilton(int k) delaet? algoritm v detaliax

    Автор сайта отвечает:
    увы, по коду. не могу. я его не сам писал, а нашел в интернете и показал на сайте..

  8. Марат:

    Программа есть. Смотрим результат.
    3—>1—>4—>2—>5—>3

    Почему? С первой вершины нет пути к четвертой?

    Автор сайта отвечает:
    ну, очевидно же, что в составлении матрицы смежности у меня допущена ошибка 🙁
    Посмотрите внимательно в матрицу. там она одна.
    Правильный ответ 3-1-2-4-5-3
    Просто 1 Ноль на единицу исправить нужно и будет как должно быть.
    ________________________________
    И спасибо, что сказали. Если не разберетесь, то сообщите, я покажу где именно я ее допустил.

  9. archie:

    Исправили бы ошибки и только потом выложили бы

  10. Аноним:

    а если у меня другой граф? как мне програму использовать?

    матрица вводитса в начале и все, не используется

    • Вопрос не очень понятен.
      Если Гамильтонов цикл и дугой граф, то делается другая матрица. Правило составления описано в статье.

  11. Кек:

    Программу писал полный мудила, стиль говно, глобальные переменные, никаких комментов… ЕЩе и не объяснил алгоритм поиска цикла

  12. Баур:

    можешь скинуть программу?

  13. Хуй:

    Что за хуйня про снайперов…

  14. кэк:

    Снайперы — это полный кринж конечно. Я поржала)))

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/mett-vaysfeld/obektno-orientirovannoe-myshlenie/?lfrom=15589587
Яндекс.Метрика