Cykl Eulera

Cykla Eulera to taki cykl w dowolnym grafie (skierowanym bądź nie), który przechodzi przez KAŻDĄ krawędź grafu dokładnie RAZ (przez wierzchołki może, a nawet musi przechodzić wiele razy). Jest kilka warunków na istnienie takiego cyklu:

• W grafie nieskierowanym:
  1. graf jest spójny
  2. z każdego wierzchołka wychodzi parzysta ilość krawędzi (parzysty stopień wierzchołka)
• W grafie skierowanym:
  1. graf jest spójny
  2. z każdego wierzchołka wychodzi tyle samo krawędzi co wchodzi (stopień wyjściowy równy wejsciowemu)

O ile sprawdzenie stopni wierzchołków nie powinno sprawić żadnych kłopotów, to już sprawdzenie spójności grafu może być problemem. Sprawdzanie Spójności Grafu.

Po spełnieniu powyższych warunków mamy pewność, że w naszym grafie istnieje Cykl Eulera. Aby go znaleźć używamy zmodyfikowanej procedury DFS, z użyciem 2 stosów. Zaczynamy przeszukiwanie z dowolnego wierzchołka, wrzucamy go na stos drogowy. Przechodzimy do kolejnego wierzchołka (normalnie tak jak w DFS) i usuwamy krawędź po której właśnie przeszliśmy (bądź oznaczamy ją jako już użytą), wierzchołek wrzucamy na stos drogowy itd. W pewnym momencie dojdziemy do wierzchołka, z którego nie da się już nigdzie dojść. Wtedy zdejmujemy ten wierzchołek ze stosu drogowego i wrzucamy go na stos cyklowy. Sprawdzamy czy z wierzchołka który teraz znajduje się na szczycie stosu da się gdzieś dojść, jeśli nie to zdejmujemy go ze stosu drogowego i wrzucamy na stos cyklowy. Tą czynność powtarzamy, aż na górze stosu drogowego bedzie wierzcholek, z ktorego wychodzi jakaś krawędź. W tym momencie powracamy do naszego DFS'a i idziemy dalej. Procedujemy według powyższego schematu, aż stos drogowy będzie pusty (nie będzie już żadnych krawędzi w grafie). Na koniec zdejmujemy wierzcholki ze stosu cyklowego i wypisujemy je. Jest to szukany Cykl Eulera.

Przykładowy kod:

#include <iostream>
#include <vector>
#include <deque>
#include <utility>
#include <map>
using namespace std;
vector<vector<int> > graf;
deque<int> drogowy, cyklowy;
map<pair<int, int>, bool> uzyte; //struktura do przechowywania uzytych krawedzi
int N, E, u, v;
int directed=0;
void eulerdfs(int s);
 
int eulervisit(int u){ //funkcja pomocnicza dla eulerdfs, odpalajaca rekurencyjnie eulerdfs dla dzieci u oraz zliczajaca ile bylo odpalen rekurencyjnych
    int counter=0;
    for(vector<int>::iterator it=graf[u].begin(); it!=graf[u].end(); it++){ //wchodzimy rekurencyjnie we wszystkie dzieci u sprawdzajac
        //czy juz nie przeszlismy wczesniej po krawedzi u->v
        int v=*it;
        if(uzyte[make_pair(u, v)]==false){ //jesli nie przeszlismy wczesniej ta krawedzia to, przejdzmy teraz
            uzyte[make_pair(u, v)]=true; //ustawiamy ze juz nia przeszlismy
            if(directed==0)uzyte[make_pair(v, u)]=true; //w przypadku grafu nieskierowanego automatycznie przeszlismy tez krawedzia odwrotna
            counter++; //zwiekszamy licznik udanych przejsc po krawedziach wychodzacych
            eulerdfs(v); //odpalamy rekurencyjnie dla dziecka
        }
    }
    return counter; //zwraca ilosc krawedzi w ktore weszlismy
}
 
void eulerdfs(int s){
    int u=s;
    drogowy.push_back(u); //dodajemy u na stos drogowy
    while(eulervisit(u)==0 && !drogowy.empty()){ //dopoki nie da sie nigdzie dojsc z u, zdejmuj kolejne wierzcholki ze stosu drogowego
        cyklowy.push_back(u); //szczytowy element z drogowego wrzucamy na stos cyklowy ....
        drogowy.pop_back(); //... i usuwamy go ze stosu drogowego
        if(!drogowy.empty())u=drogowy.back(); //u jest teraz aktualnym szczytowym elementem stosu drogowego
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin>>N>>E>>directed;
    graf.resize(N);
    drogowy.clear();
    cyklowy.clear();
    for(int i=0; i<E; i++){
        cin>>u>>v;
        graf[u-1].push_back(v-1);
        if(directed==0)graf[v-1].push_back(u-1);
    }
    //Sprawdz spojnosc grafu i zlicz stopnie wierzcholkow. Jesli wszystko zgadza sie z wymogami, kontynuuj
    eulerdfs(0);
    cout<<"Cykl Eulera tworzy nastepujaca droga: "<<endl;
    while(!cyklowy.empty()){
        cout<<cyklowy.front()+1<<" ";
        cyklowy.pop_front();
    }
    cout<<endl;
    system("pause");
    return 0;
}
//Przykladowe wejście
/*5 6 0
1 2
1 3
2 3
2 4
2 5
4 5*/