Графы. Эйлеров цикл в C++

Эйлеров цикл в C++
Второе мое знакомство с графами получилось знакомством с Эйлеровым циклом. Эйлеров цикл может представлять собой злой и жестокий курсач, который способен доводить до нервных срывов. Проблема в том, что многие из нас далеко не математики, но от программистов требуют очень сильных математических знаний.
Признаюсь честно, я не знаю как код работает и полностью код объяснить не могу. Но несмотря на это, я покажу исходник, который может оказаться полезным в изучении графов. Написал этот код не я. Но я его слегка переделывал.

Как и всегда я не буду описывать как в учебниках. Как-то там не по-русски всё. Почитывая учебники иногда создается впечатление, что автор писал для избранных. В интернете я еле нашел рабочий и понятный мне пример, которым я и делюсь. Здесь пример для Borland C++ 3.1 dos, но маленькая правка и пример работает в Visual Studio. Я проверил)

Исследуемый граф.

Эйлеров граф в C++  

МАТРИЦА СМЕЖНОСТИ
ДЛЯ ЭТОГО ГРАФА
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

 

Надеюсь вы понимаете, что такое матрица смежности и почему она такая.

Давайте смотреть исходный код Эйлерова цикла. Ввод данных с клавиатуры

Результат:
Эйлеров цикл в C++
Хорошо, если вы понимаете что это за цифры, но наверняка найдутся те, кто не знает и сколько не говори о Кенинсбергских мостах, не поймут. Поэтому поясню. Эти цифры — это маршрут по вершинам графа, причем посещаются все ребра графа, но при этом каждое из ребер посещается только однажды. Ниже рисунок. Рёбра графа — это линии, которые соединяют кружки. Чтобы было понятнее смотрим на рисунок и ходим по стрелочкам согласно нашему результату. Еще удобнее срисовать и вычеркивать каждое пройденное ребро.
Эйлеров цикл в C++

Для существования Эйлерова цикла существуют определенные условия и их очень просто найти. То, что дал я — найти тоже можно, но искать затруднительно, поэтому этот материал об Эйлерове цикле может оказаться очень полезным.

Исходник Эйлерова цикла загружает матрицу смежности из файла и сохраняет результат в другой файл


Исходный файл текстовый документ e_graph.txt
5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Результат записывается в E_CYCLE в ту же папку где исходный файл.

11 комментариев на «“Графы. Эйлеров цикл в C++”»

  1. Юзер:

    init() то не прописана

  2. Игорь:

    Спасибо за статью. Подробные комментарии в коде очень приятны! 😛

  3. Алексей:

    Добавьте функцию init() в код программы.

    Автор сайта отвечает:
    и что она должна делать?

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

    Автор сайта отвечает:
    Там не надо никаких init
    ясно, будет время, попробую исправить свой косяк.
    когда первый комментатор про init() написал, я тупо не понял, что имеется ввиду
    только сейчас уже неизвестно когда время появится. Такие дела 🙁
     
    Там не надо никаких init
    Должно быть

  4. Алексей:

    Подскажите какие степени имеет данный граф?))

     

  5. Алекс:

    При запуске программы выдает ошибку : warning C4129: : неизвестная escape-последовательность

    в этой строчке:

    Подскажите, пожалуйста, как исправить?

    • Вот так. Только учтите, что нумерация внутри файла будет идти от нуля в то время как на рисунке нумерация от единицы. Т.е. если ориентироваться на рисунок, то то, что получится в файле, каждое значение на единичку меньше ожидаемого. Так что не кричите сразу, что выдает не то.

  6. Тетьяна:

    Большое спасибо! Автору респект! Реально помог =****

  7. Shel:

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

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

  8. Женя:

    Добрый день
    А как сильно меняется код, если граф ориентированный?

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

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

Поиск

 
     

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

https://www.litres.ru/robin-nikson/sozdaem-dinamicheskie-veb-sayty-s-pomoschu-php-mysql-javascript-i-css-2/?lfrom=15589587
Яндекс.Метрика