Графы. Эйлеров цикл в 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 в ту же папку где исходный файл.

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

10 комментариев: Графы. Эйлеров цикл в C++

  • Юзер говорит:

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

  • Игорь говорит:

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

  • Алексей говорит:

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

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

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

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

  • Алексей говорит:

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

     

  • Алекс говорит:

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

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

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

    • admin говорит:

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

  • Тетьяна говорит:

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

  • Shel говорит:

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

    • admin говорит:

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

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

Ваш e-mail не будет опубликован.

Поиск

 
     
Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

- Что за ошибка? Врубиться не могу никак. Помоги, а? core.cpp(252): error C2059: syntax error : ')' - Это компилятор уже не знает что тебе сказать. Дословный перевод: "я плакалъ".

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок