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

Опубликовано 13.12.2012 | Автор: admin

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

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

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

МАТРИЦА СМЕЖНОСТИ ДЛЯ ЭТОГО ГРАФА 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++

#include <iostream.h> #include <stdlib.h> struct Node { int inf; Node *next; }; //============================Stack============================== void push(Node *&st,int dat) { // Загрузка числа в стек Node *el = new Node; el->inf = dat; el->next = st; st=el; } int pop(Node *&st) { // Извлечение из стека int value = st->inf; Node *temp = st; st = st->next; delete temp; return value; } int peek(Node *st) { // Получение числа без его извлечения return st->inf; } //============================================================== Node **graph; // Массив списков смежности const int vertex = 1; // Первая вершина void add(Node*& list,int data) { //Добавление смежной вершины if(!list){list=new Node;list->inf=data;list->next=0;return;} Node *temp=list; while(temp->next)temp=temp->next; Node *elem=new Node; elem->inf=data; elem->next=NULL; temp->next=elem; } void del(Node* &l,int key) { // Удаление вершины key из списка if(l->inf==key){Node *tmp=l; l=l->next; delete tmp;} else { Node *tmp=l; while(tmp) { if(tmp->next) // есть следующая вершина if(tmp->next->inf==key) { // и она искомая Node *tmp2=tmp->next; tmp->next=tmp->next->next; delete tmp2; } tmp=tmp->next; } } } int eiler(Node **gr,int num) { // Определение эйлеровости графа int count; for(int i=0;i<num;i++) { //проходим все вершины count=0; Node *tmp=gr[i]; while(tmp) { // считаем степень count++; tmp=tmp->next; } if(count%2==1)return 0; // степень нечетная } return 1; // все степени четные } void eiler_path(Node **gr) { //Построение цикла Node *S = NULL;// Стек для пройденных вершин int v=vertex;// 1я вершина (произвольная) int u; push(S,v); //сохраняем ее в стек while(S) { //пока стек не пуст v = peek(S); // текущая вершина if(!gr[v]){ // если нет инцидентных ребер v=pop(S); cout<<v+1<<" "; //выводим вершину (у нас отсчет от 1, поэтому +1) } else { u=gr[v]->inf; push(S,u); //проходим в следующую вершину del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро } } } int main() { system("CLS"); cout<<"Количество вершин: "; int n; cin>>n; // Количество вершин int zn;// Текущее значение graph=new Node*[n]; for(int i=0;i<n;i++)graph[i]=NULL; for(i=0;i<n;i++) // заполняем массив списков for(int j=0;j<n;j++) { cin>>zn; if (zn) add(graph[i],j); } cout<<"\n\nРЕЗУЛЬТАТ "; if(eiler(graph,n))eiler_path(graph); else cout<<"Граф не является эйлеровым."; cout<<endl; cin.get(); cin.get(); return(0); }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

#include <iostream.h> #include <stdlib.h>   struct Node {    int inf;    Node *next; };   //============================Stack==============================   void push(Node *&st,int dat) {  // Загрузка числа в стек      Node *el = new Node;    el->inf = dat;    el->next = st;    st=el; }   int pop(Node *&st) {       // Извлечение из стека      int value = st->inf;    Node *temp = st;    st = st->next;    delete temp;      return value; }   int peek(Node *st) {     // Получение числа без его извлечения    return st->inf; }   //==============================================================   Node **graph;   // Массив списков смежности const int vertex = 1; // Первая вершина   void add(Node*& list,int data) {  //Добавление смежной вершины      if(!list){list=new Node;list->inf=data;list->next=0;return;}      Node *temp=list;    while(temp->next)temp=temp->next;    Node *elem=new Node;    elem->inf=data;    elem->next=NULL;    temp->next=elem; }   void del(Node* &l,int key) { // Удаление вершины key из списка      if(l->inf==key){Node *tmp=l; l=l->next; delete tmp;}    else         { Node *tmp=l; while(tmp)          {     if(tmp->next) // есть следующая вершина        if(tmp->next->inf==key)                   {  // и она искомая      Node *tmp2=tmp->next;              tmp->next=tmp->next->next;                delete tmp2;              }        tmp=tmp->next; }    } }   int eiler(Node **gr,int num) { // Определение эйлеровости графа      int count;    for(int i=0;i<num;i++)    {  //проходим все вершины         count=0;       Node *tmp=gr[i];   while(tmp)          {       // считаем степень             count++;     tmp=tmp->next;          }       if(count%2==1)return 0; // степень нечетная    }    return 1;   // все степени четные }   void eiler_path(Node **gr) { //Построение цикла      Node *S = NULL;// Стек для  пройденных вершин    int v=vertex;// 1я вершина (произвольная)    int u;      push(S,v); //сохраняем ее в стек    while(S)       {  //пока стек не пуст v = peek(S); // текущая вершина if(!gr[v]){ // если нет инцидентных ребер v=pop(S); cout<<v+1<<"   "; //выводим вершину  (у нас отсчет от 1, поэтому +1)       }      else       { u=gr[v]->inf; push(S,u);  //проходим в следующую вершину del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро       }    } }   int main() {   system("CLS"); cout<<"Количество вершин:  "; int n; cin>>n; // Количество вершин    int zn;// Текущее значение      graph=new Node*[n];    for(int i=0;i<n;i++)graph[i]=NULL;    for(i=0;i<n;i++)   // заполняем массив списков   for(int j=0;j<n;j++) {     cin>>zn;     if (zn) add(graph[i],j);   }   cout<<"\n\nРЕЗУЛЬТАТ  ";      if(eiler(graph,n))eiler_path(graph);    else cout<<"Граф не является эйлеровым.";      cout<<endl;    cin.get();    cin.get();    return(0);   }

Результат:

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

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

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

C++

#include <iostream.h> #include <stdio.h> struct Node { int inf; Node *next; }; //============================Stack============================== void push(Node *&st,int dat) { // Загрузка числа в стек Node *el = new Node; el->inf = dat; el->next = st; st=el; } int pop(Node *&st) { // Извлечение из стека int value = st->inf; Node *temp = st; st = st->next; delete temp; return value; } int peek(Node *st) { // Получение числа без его извлечения return st->inf; } //============================================================== Node **graph; // Массив списков смежности const int vertex = 1; // Первая вершина FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл void add(Node*& list,int data) { //Добавление смежной вершины if(!list){list=new Node;list->inf=data;list->next=0;return;} Node *temp=list; while(temp->next) temp=temp->next; Node *elem=new Node; elem->inf=data; elem->next=NULL; temp->next=elem; } void del(Node* &l,int key) { // Удаление вершины key из списка if(l->inf==key) {Node *tmp=l; l=l->next; delete tmp;} else { Node *tmp=l; while(tmp) { if(tmp->next) // есть следующая вершина if(tmp->next->inf==key) { // и она искомая Node *tmp2=tmp->next; tmp->next=tmp->next->next; delete tmp2; } tmp=tmp->next; } } } int eiler(Node **gr,int num) { // Определение эйлеровости графа int count; for(int i=0;i<num;i++) { //проходим все вершины count=0; Node *tmp=gr[i]; while(tmp) { // считаем степень count++; tmp=tmp->next; } if(count%2==1)return 0; // степень нечетная } return 1; // все степени четные } void eiler_path(Node **gr) { //Построение цикла Node *S = NULL;// Стек для пройденных вершин int v=vertex;// 1я вершина (произвольная) int u; push(S,v); //сохраняем ее в стек while(S) { //пока стек не пуст v = peek(S); // текущая вершина if(!gr[v]){ // если нет инцидентных ребер v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину } else { u=gr[v]->inf; push(S,u); //проходим в следующую вершину del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро } } } int main() { int n; // Количество вершин int zn;// Текущее значение fscanf(fi,"%d",&n); graph=new Node*[n]; for(int i=0;i<n;i++)graph[i]=NULL; for(i=0;i<n;i++) // заполняем массив списков for(int j=0;j<n;j++) { fscanf(fi,"%d",&zn); if(zn) add(graph[i],j); } if(eiler(graph,n))eiler_path(graph); else fprintf(fo,"Граф не является эйлеровым."); return(0); }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

#include <iostream.h> #include <stdio.h>   struct Node {    int inf;    Node *next; };   //============================Stack==============================     void push(Node *&st,int dat) {  // Загрузка числа в стек      Node *el = new Node;    el->inf = dat;    el->next = st;    st=el; }   int pop(Node *&st) {       // Извлечение из стека    int value = st->inf;    Node *temp = st;    st = st->next;    delete temp;      return value; }   int peek(Node *st) {     // Получение числа без его извлечения    return st->inf; }   //==============================================================   Node **graph;   // Массив списков смежности const int vertex = 1; // Первая вершина   FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл   void add(Node*& list,int data) {  //Добавление смежной вершины      if(!list){list=new Node;list->inf=data;list->next=0;return;}    Node *temp=list;      while(temp->next)  temp=temp->next;      Node *elem=new Node;    elem->inf=data;    elem->next=NULL;    temp->next=elem; }   void del(Node* &l,int key) { // Удаление вершины key из списка      if(l->inf==key)  {Node *tmp=l; l=l->next; delete tmp;}    else      {          Node *tmp=l;          while(tmp)          {                if(tmp->next) // есть следующая вершина                if(tmp->next->inf==key)                {  // и она искомая                      Node *tmp2=tmp->next;                      tmp->next=tmp->next->next;                      delete tmp2;                }                tmp=tmp->next;          }    } }   int eiler(Node **gr,int num) { // Определение эйлеровости графа      int count;      for(int i=0;i<num;i++)    {  //проходим все вершины         count=0;       Node *tmp=gr[i];            while(tmp)         {       // считаем степень              count++;              tmp=tmp->next;         }       if(count%2==1)return 0; // степень нечетная    }    return 1;   // все степени четные }   void eiler_path(Node **gr) { //Построение цикла    Node *S = NULL;// Стек для  пройденных вершин    int v=vertex;// 1я вершина (произвольная)    int u;      push(S,v); //сохраняем ее в стек    while(S)        {  //пока стек не пуст            v = peek(S); // текущая вершина          if(!gr[v]){ // если нет инцидентных ребер          v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину        }        else        {          u=gr[v]->inf; push(S,u);  //проходим в следующую вершину          del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро       }    } }   int main() {    int n; // Количество вершин    int zn;// Текущее значение      fscanf(fi,"%d",&n); graph=new Node*[n];    for(int i=0;i<n;i++)graph[i]=NULL;      for(i=0;i<n;i++)   // заполняем массив списков          for(int j=0;j<n;j++)         {              fscanf(fi,"%d",&zn);              if(zn) add(graph[i],j);         }      if(eiler(graph,n))eiler_path(graph);    else fprintf(fo,"Граф не является эйлеровым.");      return(0); }

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

Отличная статья5 Плохая статья

Рубрика: Без рубрики

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

1. Юзер:

   20.01.2013 в 12:53 пп

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

   2

   Ответить
2. Игорь:

   17.05.2013 в 7:56 пп

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

   3

   Ответить
3. Алексей:

   28.10.2013 в 5:21 пп

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

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

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

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

   C++

   Node *S = NULL ;// Стек для пройденных вершин

   1	Node *S = NULL ;// Стек для пройденных вершин

   Ответить
4. Алексей:

   20.04.2015 в 4:32 дп

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

    

   Ответить
   • admin:

     25.04.2015 в 8:24 пп

     У каждой вершины 4 ребра, значит у каждой вершины 4-я степень.

     Ответить
5. Алекс:

   11.05.2015 в 1:26 пп

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

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

   C++

    v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину

   1	v=pop(S); fprintf(fo,"%d\ ",v); //выводим вершину

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

   2

   Ответить
   • admin:

     11.05.2015 в 4:28 пп

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

     C++

     #include <iostream> #include <cstdio> struct Node { int inf; Node *next; }; //============================Stack============================== void push(Node *&st,int dat) { // Загрузка числа в стек Node *el = new Node; el->inf = dat; el->next = st; st=el; } int pop(Node *&st) { // Извлечение из стека int value = st->inf; Node *temp = st; st = st->next; delete temp; return value; } int peek(Node *st) { // Получение числа без его извлечения return st->inf; } //============================================================== Node **graph; // Массив списков смежности const int vertex = 1; // Первая вершина FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл void add(Node*& list,int data) { //Добавление смежной вершины if(!list){list=new Node;list->inf=data;list->next=0;return;} Node *temp=list; while(temp->next) temp=temp->next; Node *elem=new Node; elem->inf=data; elem->next=NULL; temp->next=elem; } void del(Node* &l,int key) { // Удаление вершины key из списка if(l->inf==key) {Node *tmp=l; l=l->next; delete tmp;} else { Node *tmp=l; while(tmp) { if(tmp->next) // есть следующая вершина if(tmp->next->inf==key) { // и она искомая Node *tmp2=tmp->next; tmp->next=tmp->next->next; delete tmp2; } tmp=tmp->next; } } } int eiler(Node **gr,int num) { // Определение эйлеровости графа int count; for(int i=0;i<num;i++) { //проходим все вершины count=0; Node *tmp=gr[i]; while(tmp) { // считаем степень count++; tmp=tmp->next; } if(count%2==1)return 0; // степень нечетная } return 1; // все степени четные } void eiler_path(Node **gr) { //Построение цикла Node *S = NULL;// Стек для пройденных вершин int v=vertex;// 1я вершина (произвольная) int u; push(S,v); //сохраняем ее в стек while(S) { //пока стек не пуст v = peek(S); // текущая вершина if(!gr[v]){ // если нет инцидентных ребер v=pop(S); fprintf(fo,"%d ",v); //выводим вершину } else { u=gr[v]->inf; push(S,u); //проходим в следующую вершину del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро } } } int main() { int n; // Количество вершин int zn;// Текущее значение fscanf(fi,"%d",&n); graph=new Node*[n]; for(int i=0;i<n;i++)graph[i]=NULL; for(int i=0;i<n;i++) // заполняем массив списков for(int j=0;j<n;j++) { fscanf(fi,"%d",&zn); if(zn) add(graph[i],j); } if(eiler(graph,n))eiler_path(graph); else fprintf(fo,"Граф не является эйлеровым."); return(0); }

     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

     #include <iostream> #include <cstdio>   struct Node {    int inf;    Node *next; };   //============================Stack==============================     void push(Node *&st,int dat) {  // Загрузка числа в стек      Node *el = new Node;    el->inf = dat;    el->next = st;    st=el; }   int pop(Node *&st) {       // Извлечение из стека    int value = st->inf;    Node *temp = st;    st = st->next;    delete temp;      return value; }   int peek(Node *st) {     // Получение числа без его извлечения    return st->inf; }   //==============================================================   Node **graph;   // Массив списков смежности const int vertex = 1; // Первая вершина   FILE* fi = fopen("e_graph.txt","r"); //Файл с матрицей смежности FILE* fo = fopen("e_cycle.txt","w"); // Результирующий файл   void add(Node*& list,int data) {  //Добавление смежной вершины      if(!list){list=new Node;list->inf=data;list->next=0;return;}    Node *temp=list;      while(temp->next)  temp=temp->next;      Node *elem=new Node;    elem->inf=data;    elem->next=NULL;    temp->next=elem; }   void del(Node* &l,int key) { // Удаление вершины key из списка      if(l->inf==key)  {Node *tmp=l; l=l->next; delete tmp;}    else      {          Node *tmp=l;          while(tmp)          {                if(tmp->next) // есть следующая вершина                if(tmp->next->inf==key)                {  // и она искомая                      Node *tmp2=tmp->next;                      tmp->next=tmp->next->next;                      delete tmp2;                }                tmp=tmp->next;          }    } }   int eiler(Node **gr,int num) { // Определение эйлеровости графа      int count;      for(int i=0;i<num;i++)    {  //проходим все вершины         count=0;       Node *tmp=gr[i];            while(tmp)         {       // считаем степень              count++;              tmp=tmp->next;         }       if(count%2==1)return 0; // степень нечетная    }    return 1;   // все степени четные }   void eiler_path(Node **gr) { //Построение цикла    Node *S = NULL;// Стек для  пройденных вершин    int v=vertex;// 1я вершина (произвольная)    int u;      push(S,v); //сохраняем ее в стек    while(S)        {  //пока стек не пуст            v = peek(S); // текущая вершина          if(!gr[v]){ // если нет инцидентных ребер          v=pop(S); fprintf(fo,"%d ",v); //выводим вершину        }        else        {          u=gr[v]->inf; push(S,u);  //проходим в следующую вершину          del(gr[v],u); del(gr[u],v); //удаляем пройденное ребро       }    } }   int main() {    int n; // Количество вершин    int zn;// Текущее значение      fscanf(fi,"%d",&n); graph=new Node*[n];    for(int i=0;i<n;i++)graph[i]=NULL;      for(int i=0;i<n;i++)   // заполняем массив списков          for(int j=0;j<n;j++)         {              fscanf(fi,"%d",&zn);              if(zn) add(graph[i],j);         }      if(eiler(graph,n))eiler_path(graph);    else fprintf(fo,"Граф не является эйлеровым.");      return(0); }

     Ответить
6. Тетьяна:

   25.10.2016 в 10:17 пп

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

   Ответить
7. Shel:

   03.05.2017 в 4:18 пп

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

   Ответить
   • admin:

     03.05.2017 в 7:15 пп

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

     Ответить
8. Женя:

   25.12.2019 в 3:25 дп

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

   Ответить