Znajdowanie cyklu lub ścieżki Eulera


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Algorytm dla spójnych grafów nieskierowanych
Algorytm Fleury'ego
Algorytm Hierholzera

Problem

W danym grafie znaleźć cykl lub ścieżkę Eulera, jeśli istnieją.



Przypomnijmy:

 

Cykl Eulera (ang. Eulerian circuit, Eulerian cycle lub Eulerian tour) jest ścieżką, która przechodzi dokładnie jeden raz przez każdą krawędź grafu i kończy się w wierzchołku, od którego się rozpoczęła.

Ścieżka Eulera (ang. Eulerian path, Eulerian trail lub Eulerian walk) to ścieżka, która przechodzi dokładnie jeden raz przez każdą krawędź grafu, lecz kończy się w innym wierzchołku niż w startowym.

 

Istnienie cyklu lub ścieżki Eulera dokładnie opisaliśmy w poprzednim rozdziale. Tutaj naszym zadaniem będzie wyznaczenie tego cyklu lub ścieżki.

Algorytm dla grafów spójnych nieskierowanych

Dla grafów nieskierowanych istnieje bardzo prosty algorytm wyznaczania cyklu Eulera (cykl taki musi istnieć w grafie, inaczej algorytm zawodzi). Opiera się on na stosie oraz rekurencyjnym przejściu DFS postorder.

 

Graf przechodzimy przy pomocy rekurencyjnej procedury DFS. Przebyte krawędzie usuwamy, a wierzchołki po zakończeniu przetwarzania umieszczamy na stosie. Jeśli graf posiada cykl Eulera, to po zakończeniu algorytmu na stosie znajdą się kolejne wierzchołki tego cyklu.

 

Algorytm znajdowania cyklu Eulera w spójnym grafie nieskierowanym

Procedura rekurencyjna DFSEuler(graf,v,S)
Dane wejściowe
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
v  – numer wierzchołka grafu, v C
S  – stos wierzchołków
Dane wyjściowe
S - zawierająca numery kolejnych wierzchołków w jednym z cykli Eulera
Lista kroków rekurencyjnej procedury DFSEuler(v)
K01: Dla każdego sąsiada u wierzchołka v wykonuj K02...K03 Przeglądamy listę sąsiedztwa
K02:     Usuń z grafu krawędź v–u Każdą krawędź usuwamy, aby nie była wykorzystana dwukrotnie
K03:     DFSEuler(graf,u,S) Rekurencyjnie wywołujemy procedurę DFS
K04: S.push(v) Po przetworzeniu, wierzchołek umieszczamy na stosie
K05: Zakończ  

 

Uwaga: algorytm wymaga usuwania krawędzi z grafu. Najprostszym rozwiązaniem jest tutaj zastosowanie macierzy sąsiedztwa, w której element ai,j określa liczbę krawędzie pomiędzy wierzchołkiem i-tym a j-tym. Takie podejscie umożliwia szukanie cykli Eulera w multigrafach.

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu nieskierowanego, tworzy macierz sąsiedztwa i szuka Cyklu Eulera. Znaleziony cykl jest wyświetlany w oknie konsoli.

 

Przykładowe dane dla programu:

Graf z cyklem Eulera

6 10
0 4 0 5
1 2 1 3 1 4 1 5
2 3 2 4 2 5
4 5

 

Lazarus
// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program EulerCycle;

// Typy dla dynamicznej macierzy sąsiedztwa
type
  nptr = array of integer;  // Wiersz

// Zmienne globalne
var
  n,m,sptr : integer;
  A   : array of nptr;          // Macierz sąsiedztwa
  S   : array of integer;       // Stos w tablicy

// Procedura wyszukuje cykl Eulera
// We:
// v - wierzchołek startowy
//--------------------------------
procedure DFSEuler(v : integer);
var
  i : integer;
begin
  for i := 0 to n - 1 do          // Przeglądamy sąsiadów
    while A[v][i] > 0 do
    begin
      dec(A[v][i]);               // Usuwamy krawędź
      dec(A[i][v]);
      DFSEuler(i);                // Rekurencja
    end;
  S[sptr] := v;                   // Wierzchołek v umieszczamy na stosie
  inc(sptr);
end;

// **********************
// *** Program główny ***
// **********************

var
  i,j,v1,v2 : integer;
begin
  read(n,m);                    // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);               // Tworzymy tablicę wskaźników
  SetLength(S,m+1);             // Tworzymy stos
  sptr := 0;

  for i := 0 to n - 1 do
    SetLength(A[i],n);          // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
    for j := 0 to n - 1 do A[i][j] := 0;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read(v1,v2);        // wierzchołki końcowe krawędzi
    inc(A[v1][v2]);     // Krawędź v1->v2 obecna
    inc(A[v2][v1]);     // Krawędź v2->v1 obecna
  end;

  writeln;

  // Wyznaczamy cykl Eulera

  DFSEuler(0);

  // Wypisujemy zawartość stosu

  write('EULERIAN CYCLE : ');

  for i := 0 to sptr - 1 do write(S[i],' ');
  writeln;

  // Usuwamy tablice dynamiczne

  for i := 0 to n - 1 do SetLength(A[i],0);
  SetLength(A,0);
  SetLength(S,0);
end.
Code::Blocks
// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Zmienne globalne

int n,m,sptr;
int ** A;                       // Macierz sąsiedztwa
int * S;                        // Stos w tablicy

// Procedura wyszukuje cykl Eulera
// We:
// v - wierzchołek startowy
//--------------------------------
void DFSEuler(int v)
{
  int i;

  for(i = 0; i < n; i++)          // Przeglądamy sąsiadów
    while(A[v][i])
    {
      A[v][i]--;                  // Usuwamy krawędź
      A[i][v]--;
      DFSEuler(i);                // Rekurencja
    }
  S[sptr++] = v;                  // Wierzchołek v umieszczamy na stosie
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i,j,v1,v2;

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  A = new int * [n];            // Tworzymy tablicę wskaźników
  S = new int [m + 1];          // Tworzymy stos
  sptr = 0;

  for(i = 0; i < n; i++)
    A[i] = new int [n];         // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A[i][j] = 0;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // wierzchołki końcowe krawędzi
    A[v1][v2]++;        // Krawędź v1->v2 obecna
    A[v2][v1]++;        // Krawędź v2->v1 obecna
  }

  cout << endl;

  // Wyznaczamy cykl Eulera

  DFSEuler(0);

  // Wypisujemy zawartość stosu

  cout << "EULERIAN CYCLE : ";

  for(i = 0; i < sptr; i++) cout << S[i] << " ";
  cout << endl;

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++) delete [] A[i];

  delete [] A;
  delete [] S;

  return 0;
}
Free Basic
' Wyszukiwanie cyklu Eulera
' Data: 19.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne

Dim Shared As Integer n,m,sptr
Dim Shared As Integer Ptr Ptr A ' Macierz sąsiedztwa
Dim Shared As Integer Ptr S     ' Stos w tablicy

' Procedura wyszukuje cykl Eulera
' We:
' v - wierzchołek startowy
'--------------------------------
Sub DFSEuler(byval v As Integer)
  
  Dim As Integer i

  For i = 0 To n - 1              ' Przeglądamy sąsiadów
    While A[v][i]
      A[v][i] -= 1                ' Usuwamy krawędź
      A[i][v] -= 1
      DFSEuler(i)                 ' Rekurencja
    Wend
  Next
  S[sptr] = v                     ' Wierzchołek v umieszczamy na stosie
  sptr += 1
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As integer i,j,v1,v2

Open Cons For Input As #1

Input #1,n,m                      ' Czytamy liczbę wierzchołków i krawędzi

A = New integer Ptr [n]           ' Tworzymy tablicę wskaźników
S = New Integer [m + 1]           ' Tworzymy stos
sptr = 0

For i = 0 To n - 1
  A[i] = New Integer [n]          ' Tworzymy wiersze macierzy sąsiedztwa
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  For j = 0 To n - 1
  	 A[i][j] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  Input #1,v1,v2       ' wierzchołki końcowe krawędzi
  A[v1][v2] += 1       ' Krawędź v1->v2 obecna
  A[v2][v1] += 1       ' Krawędź v2->v1 obecna
Next

Print

Close #1

' Wyznaczamy cykl Eulera

DFSEuler(0)

' Wypisujemy zawartość stosu

Print "EULERIAN CYCLE :";

For i = 0 To sptr - 1
  Print S[i];
Next
Print

' Usuwamy tablice dynamiczne

For i = 0 To n - 1
  Delete [] A[i]
Next

Delete [] A
Delete [] S

End
Wynik
6 10
0 4 0 5
1 2 1 3 1 4 1 5
2 3 2 4 2 5
4 5

EULERIAN CYCLE : 0 5 4 2 5 1 3 2 1 4 0

 

Algorytm Fleury'ego

Dosyć prostym algorytmem znajdowania cyklu lub ścieżki Eulera jest algorytm Fleury'ego. W czasie pracy korzysta on ze znajdowania mostów. Zasada działania dla cyklu Eulera (graf musi taki cykl posiadać, co można z kolei sprawdzić algorytmem opisanym w poprzednim rozdziale) jest następująca:

 

Wybieramy dowolny wierzchołek w grafie o niezerowym stopniu. Będzie to wierzchołek startowy cyklu Eulera. Następnie wybieramy krawędź, która nie jest mostem (przejście przez most oznacza brak możliwości powrotu do tego wierzchołka, zatem jeśli zostały w nim nieodwiedzone krawędzie, to tych krawędzi już byśmy nie odwiedzili i cykl Eulera nie zostałby znaleziony), chyba że nie mamy innego wyboru, tzn. pozostała nam jedynie krawędź-most. Zapamiętujemy tę krawędź na liście lub na stosie. Przechodzimy wybraną krawędzią do kolejnego wierzchołka grafu. Przebytą krawędź usuwamy z grafu. W nowym wierzchołku całą procedurę powtarzamy, aż zostaną przebyte wszystkie krawędzie.

 

Aby lepiej zrozumieć zasadę działania algorytmu Fleury'ego, prześledźmy kolejne operacje:

 

S: Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste.
S: 0 Jako punkt startowy możemy wybrać dowolny wierzchołek o stopniu niezerowym. Wybierzmy zatem wierzchołek 0 i wpiszmy go na stos, który będzie zawierał kolejno odwiedzane wierzchołki w cyklu.

Z wierzchołka 0 prowadzą dwie krawędzie do wierzchołków 4 i 5. Żadna nie jest mostem, zatem możemy wybrać dowolną z nich. Wybieramy krawędź prowadzącą do wierzchołka 4, przechodzimy do tego wierzchołka, a krawędź usuwamy.

S: 4 0 Jesteśmy w wierzchołku 4. Umieszczamy go na stosie.

W wierzchołku 4 mamy krawędzie do wierzchołków 1, 2 i 5 (krawędź do 0 została usunięta!). Żadna z nich nie jest mostem, zatem wybieramy krawędź do wierzchołka 1, przechodzimy do niego i krawędź usuwamy.

S: 1 4 0 Wierzchołek 1 umieszczamy na stosie.

Żadna z krawędzi do wierzchołków 2, 3 i 5 nie jest mostem. Wybieramy krawędź do wierzchołka 2, przechodzimy do wierzchołka 2, a krawędź usuwamy z grafu.

S: 2 1 4 0 Wierzchołek 2 dopisujemy do stosu.

Krawędzie do wierzchołków 3, 4 i 5 nie są mostami. Wybieramy krawędź do wierzchołka 3, przechodzimy do niego i usuwamy przebytą krawędź.

S: 3 2 1 4 0 Wierzchołek 3 dopisujemy do stosu.

W wierzchołku 3 pozostała tylko krawędź do wierzchołka 1. Jest ona mostem, lecz nie mamy innego wyboru. Idziemy zatem do wierzchołka 1, a krawędź usuwamy.

S: 1 3 2 1 4 0 Wierzchołek 1 dopisujemy do stosu.

Krawędź do wierzchołka 5 również jest mostem, ale nie mamy innego wyboru. Idziemy do wierzchołka 5 i usuwamy krawędź.

S: 5 1 3 2 1 4 0 Wierzchołek 5 dopisujemy do stosu.

Krawędź do wierzchołka 0 jest mostem, tej nie możemy wybrać, ponieważ mamy też inne krawędzie, które nie są mostami: do wierzchołków 2 i 4. Wybieramy krawędź do wierzchołka 2, przechodzimy do niego, krawędź usuwamy z grafu.

S: 2 5 1 3 2 1 4 0 Wierzchołek 2 dopisujemy do stosu.
Pozostała nam tylko krawędź do wierzchołka 4. Przechodzimy do niego, krawędź usuwamy.
S: 4 2 5 1 3 2 1 4 0 Wierzchołek 4 dopisujemy do stosu, przechodzimy do wierzchołka 5 i usuwamy krawędź.
S: 5 4 2 5 1 3 2 1 4 0 Wierzchołek 5 dopisujemy do stosu, przechodzimy do wierzchołka 0 i usuwamy krawędź.
S: 0 5 4 2 5 1 3 2 1 4 0 Wierzchołek 0 dopisujemy do stosu. Ponieważ nie ma już dalszych krawędzi, algorytm kończymy. Na stosie zapisany jest ciąg wierzchołków cyklu Eulera w odwrotnej kolejności odwiedzin (dla grafu nieskierowanego zwrot cyklu Eulera nie ma znaczenia).

 

Algorytm Fleury'ego jest elegancki i łatwy do zrozumienia, jednakże niezbyt efektywny, ponieważ wymaga wyznaczania mostów w każdym odwiedzanym wierzchołku (wyznaczanie mostów możemy pominąć, jeśli wierzchołek ma tylko jednego sąsiada – do wyznaczania tych mostów można użyć podanego wcześniej algorytmu Tarjana, który działa w czasie liniowym).

 

Ten sam algorytm Fleury'ego można zastosować do znajdowania ścieżki Eulera. W tym przypadku rozpoczynamy w węźle o nieparzystym stopniu. Reszta jest identyczna jak dla cyklu Eulera.

 

Algorytm Fleury'ego znajdowania cyklu lub ścieżki Eulera w grafie nieskierowanym

Funkcja rekurencyjna DFSb(v,vf,graf,D,cv)
Wejście
v  –  wierzchołek startowy, v C
vf  –  ojciec wierzchołka v na drzewie rozpinającym w głąb, vf C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
D    tablica numerów DFS dla poszczególnych wierzchołków
cv    referencja do zmiennej zewnętrznej przechowującej numery wierzchołków. Przy pierwszym wywołaniu zmienna powinna zawierać 1. cv C
Wyjście:
Wartość parametru Low dla wierzchołka v. Znajduje wszystkie krawędzie-mosty i odpowiednio je oznacza
Elementy pomocnicze:
Low    wartość parametru Low dla bieżącego wierzchołka, Low C
temp    chwilowo przechowuje wynik wywołania rekurencyjnego, t C
Lista kroków:
K01: D[v] ← cv ; numerujemy wierzchołek
K02 Low ← cv ; wstępna wartość parametru
K03: cv ← cv + 1 ; kolejny wierzchołek będzie miał numer o 1 większy
K04: Dla każdego sąsiada u wierzchołka v, wykonuj K05...K10 ; przeglądamy wszystkich sąsiadów wierzchołka bieżącego
K05:     Jeśli u = vf, to następny obieg pętli K04 ; pomijamy ojca na drzewie rozpinającym
K06:     Jeśli D[u] = 0, to idź do K09 ; sąsiad nieodwiedzony?
K07:     Jeśli D[u] < Low, to LowD[u] ; odwiedzony, krawędź wtórna. Modyfikujemy parametr Low
K08:     Następny obieg pętli K04  
K09:     temp ← DFSb(u,v,graf,T,D,cv) ; rekurencyjne wywołanie funkcji
K10:     Jeśli temp < Low, to Lowtemp ; modyfikujemy parametr Low
K11: Jeśli (vf > -1) (Low = D[v]), to oznacz krawędź vf-v jako most ; sąsiedzi odwiedzeni. Sprawdzamy warunek mostu
K12: Zakończ z wynikiem Low  
 
Algorytm główny
Wejście
v  –  numer wierzchołka startowego, n C.
Dla cyklu Eulera jest to wierzchołek dowolny o niezerowym stopniu parzystym.
Dla ścieżki Eulera jest to wierzchołek o nieparzystym stopniu
n  –  liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
Graf musi posiadać cykl lub ścieżkę Eulera, co można sprawdzić innym algorytmem.
Wyjście:
S    stos zawiera kolejno odwiedzone wierzchołki cyklu lub ścieżki Eulera
Elementy pomocnicze:
cv    przechowuje numery wierzchołków dla DFS, cv C
D    dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi.
u    numer wierzchołka w grafie, u,w C
Lista kroków:
K01: Utwórz n elementową tablicę D  
K02: Utwórz pusty stos S  
K03:     S.push(v) ; wierzchołek v na stos
K04:     Jeśli v nie ma sąsiadów, to zakończ ; koniec cyklu lub ścieżki
K05:     u ← pierwszy sąsiad v  
K06:     Wyzeruj tablicę D ; inaczej musimy wyszukać mosty
K07:     cv ← 1  
K08:     DFSb(v,-1,graf,D,cv) ; szukamy mostów
K09:     Dopóki v-u jest mostem i istnieje następny sąsiad, wykonuj:
        u ← następny sąsiad
; szukamy krawędzi, która nie jest mostem
K10:     Usuń krawędź v-u z grafu ; przebytą krawędź usuwamy
K11     vu ; przechodzimy do wierzchołka u
K12: Idź do K03 ; i wracamy na początek pętli

 

Aby stworzyć implementację tego algorytmu, należy rozwiązać dwa problemy:

  1. Jak efektywnie usuwać krawędzie z grafu? Najprostsze rozwiązanie to reprezentacja grafu w postaci macierzy sąsiedztwa. W tej reprezentacji komórka A[u,v] macierzy określa istnienie krawędzi u-v. Jeśli ma wartość 0, krawędź nie istnieje. W przeciwnym razie krawędź istnieje. Wystarczy zatem po prostu zerować te komórki.
  2. Jak oznaczać krawędź most? W reprezentacji macierzą sąsiedztwa możemy się umówić, że komórka A[u,v] o wartości 1 oznacza normalną krawędź u-v, a gdy wartość będzie równa 2, to mamy do czynienia z krawędzią-mostem. W tym rozwiązaniu algorytm DFS dla krawędzi-mostów w macierzy sąsiedztwa umieści wartość 2.

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu nieskierowanego, tworzy macierz sąsiedztwa, wyznacza stopnie wierzchołków. Jeśli stopnie wszystkich wierzchołków są parzyste, to szuka cyklu Eulera. W przeciwnym razie szuka ścieżki Eulera, rozpoczynając od wierzchołka o stopniu nieparzystym. Graf wejściowy musi taki cykl lub ścieżkę zawierać – program tego nie sprawdza (test na istnienie cyklu lub ścieżki Eulera opisaliśmy w poprzednim rozdziale). Cykl lub ścieżka są wypisywane w postaci ciągu kolejno odwiedzanych wierzchołków.

 

Przykładowe dane dla programu:

Graf z cyklem Eulera

symbol

9 14
1 4 1 6
2 3 2 5
3 4 3 5 3 7
4 5 4 6 4 7 4 8
5 6
6 7
7 8
       Graf ze ścieżką Eulera

symbol

9 13
0 1 0 6
1 4 1 6 1 8
2 7 2 8
4 6 4 7
5 7 5 8
6 7
7 8

 

Lazarus
// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program fleury;

// Typy dla dynamicznej macierzy
type
  nptr = array of byte;  // Wiersz

// Zmienne globalne
var
  n,m,cv,sptr : integer;
  A   : array of nptr;          // Macierz sąsiedztwa
  S   : array of integer;       // Stos w tablicy
  D   : array of integer;       // Tablica numerów wierzchołków

// Funkcja wyszukująca mosty w grafie
// We:
// v  - numer wierzchołka startowego
// vf - ojciec wierzchołka v na drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//---------------------------------------------------
function DFSb(v,vf : integer) : integer;
var
  Low,temp,i : integer;
begin
  D[v] := cv;                   // Numerujemy wierzchołek
  Low  := cv;                   // Wstępna wartość Low
  inc(cv);                      // Numer dla następnego wierzchołka
  for i := 0 to n - 1 do        // Przeglądamy sąsiadów v
    if (A[v][i] > 0) and (i <> vf) then
    begin
      if D[i] = 0 then          // Jeśli sąsiad nieodwiedzony, to
      begin
        temp :=DFSb(i,v);       // to wywołujemy rekurencyjnie DFSb()
        if temp < Low then Low := temp; // Modyfikujemy Low
      end
      else if D[i] < Low then Low := D[i];
    end;

  if (vf > -1) and (Low = D[v]) then // Mamy most?
  begin
    A[vf][v] := 2;              // Oznaczamy krawędź vf-v jako most
    A[v][vf] := 2;
  end;

  DFSb := Low;
end;

// Procedura wyszukuje cykl lub ścieżkę Eulera
// We:
// v - wierzchołek startowy
//--------------------------------------------
procedure findEuler(v : integer);
var
  u,w,i : integer;
begin
  while true do                 // W pętli przetwarzamy graf
  begin
    S[sptr] := v;               // v umieszczamy na stosie
    inc(sptr);

    u := 0;                     // Szukamy pierwszego sąsiada v
    while (u < n) and (A[v][u] = 0) do inc(u);
 
    if u = n then break;        // Nie ma sąsiadów, kończymy

    for i := 0 to n - 1 do D[i] := 0; // Zerujemy tablicę D

    cv := 1;                    // Numer pierwszego wierzchołka dla DFS
    DFSb(v,-1);                 // Identyfikujemy krawędzie-mosty

    // Szukamy krawędzi nie będącej mostem

    w := u + 1;
    while (A[v][u] = 2) and (w < n) do
    begin
      if A[v][w] > 0 then u := w;
      inc(w);
    end;

    A[v][u] := 0;               // Usuwamy krawędź v-u
    A[u][v] := 0;
    v := u;                     // Przechodzimy do u
  end;
end;

// **********************
// *** Program główny ***
// **********************

var
  i,j,v1,v2 : integer;
  VD : array of integer;        // Stopnie wierzchołków
begin
  read(n,m);                    // Czytamy liczbę wierzchołków i krawędzi

  SetLength(A,n);               // Tworzymy tablicę wskaźników
  for i := 0 to n - 1 do
    SetLength(A[i],n);          // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
    for j := 0 to n - 1 do A[i][j] := 0;

  SetLength(VD,n);              // Tworzymy tablicę stopni
  for i := 0 to n - 1 do        // Zerujemy tablicę stopni
    VD[i] := 0;

  SetLength(D,n);               // Tworzymy tablicę numerów

  SetLength(S,m+1);             // Tworzymy pusty stos
  sptr := 0;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read(v1,v2);        // Wierzchołek startowy i końcowy krawędzi
    A[v1][v2] := 1;     // Krawędź v1->v2 obecna
    A[v2][v1] := 1;     // Krawędź v2->v1 obecna
    inc(VD[v1]);
    inc(VD[v2]);        // Obliczamy stopnie v1 i v2
  end;

  writeln;

  // Szukamy pozycji startowej v1

  for v1 := 0 to n - 1 do
    if VD[v1] > 0 then break;

  for i := v1 to n - 1 do
    if VD[i] mod 2 = 1 then
    begin
      v1 := i;
      break;
    end;

  // Wyznaczamy cykl lub ścieżkę Eulera

  findEuler(v1);

  // Wypisujemy zawartość stosu

  if VD[v1] mod 2 = 1 then write('EULERIAN PATH :') else write('EULERIAN CYCLE :');
  
  for i := 0 to sptr - 1 do write(S[i]:3);
  writeln;

  // Usuwamy tablice dynamiczne

  for i := 0 to n - 1 do SetLength(A[i],0);
  SetLength(A,0);
  SetLength(S,0);
  SetLength(D,0);
  SetLength(VD,0);
end.
Code::Blocks
// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Zmienne globalne

int n,m,cv,sptr;
char **A;                       // Macierz sąsiedztwa
int *S;                         // Stos w tablicy
int *D;                         // Tablica numerów wierzchołków

// Funkcja wyszukująca mosty w grafie
// We:
// v  - numer wierzchołka startowego
// vf - ojciec wierzchołka v na drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//---------------------------------------------------
int DFSb(int v,int vf)
{
  int Low,temp,i;

  D[v] = cv;                    // Numerujemy wierzchołek
  Low  = cv;                    // Wstępna wartość Low
  cv++;                         // Numer dla następnego wierzchołka
  for(i = 0; i < n; i++)        // Przeglądamy sąsiadów v
    if(A[v][i] && (i != vf))
    {
      if(!D[i])                 // Jeśli sąsiad nieodwiedzony, to
      {
        temp = DFSb(i,v);       // to wywołujemy rekurencyjnie DFSb()
        if(temp < Low) Low = temp; // Modyfikujemy Low
      }
      else if(D[i] < Low) Low = D[i];
    }

  if((vf > -1) && (Low == D[v])) // Mamy most?
    A[vf][v] = A[v][vf] = 2;    // Oznaczamy krawędź vf-v jako most

  return Low;
}

// Procedura wyszukuje cykl lub ścieżkę Eulera
// We:
// v - wierzchołek startowy
//--------------------------------------------
void findEuler(int v)
{
  int u,w,i;

  while(true)                   // W pętli przetwarzamy graf
  {
    S[sptr++] = v;              // v umieszczamy na stosie

    for(u = 0;(u < n) && !A[v][u];u++); // Szukamy pierwszego sąsiada v

    if(u == n) break;           // Nie ma sąsiadów, kończymy

    for(i = 0; i < n; i++) D[i] = 0; // Zerujemy tablicę D

    cv = 1;                     // Numer pierwszego wierzchołka dla DFS
    DFSb(v,-1);                 // Identyfikujemy krawędzie-mosty

    // Szukamy krawędzi nie będącej mostem

    for(w = u + 1;(A[v][u] == 2) && (w < n); w++)
      if(A[v][w]) u = w;

    A[v][u] = A[u][v] = 0;      // Usuwamy krawędź v-u
    v = u;                      // Przechodzimy do u
  }
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i,j,v1,v2;
  int *VD;                      // Stopnie wierzchołków

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  A = new char * [n];           // Tworzymy tablicę wskaźników
  for(i = 0; i < n; i++)
    A[i] = new char [n];        // Tworzymy wiersze macierzy sąsiedztwa

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++) A[i][j] = 0;

  VD = new int [n];             // Tworzymy tablicę stopni
  for(i = 0; i < n; i++)        // Zerujemy tablicę stopni
    VD[i] = 0;

  D = new int [n];              // Tworzymy tablicę numerów

  S = new int [m + 1];          // Tworzymy pusty stos
  sptr = 0;

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    A[v1][v2] = 1;      // Krawędź v1->v2 obecna
    A[v2][v1] = 1;      // Krawędź v2->v1 obecna
    VD[v1]++;
    VD[v2]++;           // Obliczamy stopnie v1 i v2
  }

  cout << endl;

  // Szukamy pozycji startowej v1

  for(v1 = 0; v1 < n; v1++)
    if(VD[v1]) break;

  for(i = v1; i < n; i++)
    if(VD[i] % 2)
    {
      v1 = i;
      break;
    }

  // Wyznaczamy cykl lub ścieżkę Eulera

  findEuler(v1);

  // Wypisujemy zawartość stosu

  if(VD[v1] % 2) cout << "EULERIAN PATH :"; else cout << "EULERIAN CYCLE :";

  for(i = 0; i < sptr; i++) cout << setw(3) << S[i];
  cout << endl;

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++) delete [] A[i];
  delete [] A;
  delete [] S;
  delete [] D;
  delete [] VD;

  return 0;
}
Free Basic
' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Fleury'ego
' Data: 8.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne

Dim Shared As Integer n,m,cv,sptr
Dim Shared As Byte Ptr Ptr  A   ' Macierz sąsiedztwa
Dim Shared As Integer Ptr S     ' Stos w tablicy
Dim Shared As Integer Ptr D     ' Tablica numerów wierzchołków

' Funkcja wyszukująca mosty w grafie
' We:
' v  - numer wierzchołka startowego
' vf - ojciec wierzchołka v na drzewie rozpinającym
' Wy:
' Parametr Low dla wierzchołka v
'---------------------------------------------------
function DFSb(ByVal v As integer,ByVal vf As integer) As Integer

  Dim As Integer Low,temp,i

  D[v] = cv                     ' Numerujemy wierzchołek
  Low  = cv                     ' Wstępna wartość Low
  cv += 1                       ' Numer dla następnego wierzchołka
  For i = 0 To n - 1            ' Przeglądamy sąsiadów v
    If (A[v][i] > 0) AndAlso (i <> vf) Then
      If D[i] = 0 Then          ' Jeśli sąsiad nieodwiedzony, to
        temp = DFSb(i,v)        ' to wywołujemy rekurencyjnie DFSb()
        If temp < Low Then Low = temp ' Modyfikujemy Low
      Else
        If D[i] < Low Then Low = D[i]
      End If
    End If
  Next
  
  If (vf > -1) AndAlso (Low = D[v]) Then ' Mamy most?
    A[vf][v] = 2: A[v][vf] = 2  ' Oznaczamy krawędź vf-v jako most
  End If
  
  Return Low
End Function

' Procedura wyszukuje cykl lub ścieżkę Eulera
' We:
' v - wierzchołek startowy
'--------------------------------------------
Sub findEuler(ByVal v As integer)

  Dim As Integer u,w,i

  While 1                       ' W pętli przetwarzamy graf
    S[sptr] = v                 ' v umieszczamy na stosie
    sptr += 1

    u = 0
    While (u < n) AndAlso (A[v][u] = 0) ' Szukamy pierwszego sąsiada v
      u += 1
    Wend
    
    If u = n Then Exit While    ' Nie ma sąsiadów, kończymy

    For i = 0 To n - 1
      D[i] = 0                  ' Zerujemy tablicę D
    Next

    cv = 1                      ' Numer pierwszego wierzchołka dla DFS
    DFSb(v,-1)                  ' Identyfikujemy krawędzie-mosty

    ' Szukamy krawędzi nie będącej mostem

    w = u + 1
    While (A[v][u] = 2) AndAlso (w < n)
      If A[v][w] > 0 Then u = w
      w += 1
    Wend
    
    A[v][u] = 0: A[u][v] = 0    ' Usuwamy krawędź v-u
    v = u                       ' Przechodzimy do u
  Wend
End Sub

' **********************
' *** Program główny ***
' **********************

Dim As Integer i,j,v1,v2
Dim As Integer Ptr VD           ' Stopnie wierzchołków

Open Cons For Input As #1

Input #1,n,m                    ' Czytamy liczbę wierzchołków i krawędzi

A = New Byte Ptr [n]            ' Tworzymy tablicę wskaźników
For i = 0 To n - 1
  A[i] = New Byte [n]           ' Tworzymy wiersze macierzy sąsiedztwa
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  For j = 0 To n - 1
  	 A[i][j] = 0
  Next
Next

VD = New integer [n]            ' Tworzymy tablicę stopni
For i = 0 To n - 1              ' Zerujemy tablicę stopni
  VD[i] = 0
Next

D = New integer [n]             ' Tworzymy tablicę numerów

S = New integer [m + 1]         ' Tworzymy pusty stos
sptr = 0

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  Input #1,v1,v2                ' Wierzchołek startowy i końcowy krawędzi
  A[v1][v2] = 1                 ' Krawędź v1->v2 obecna
  A[v2][v1] = 1                 ' Krawędź v2->v1 obecna
  VD[v1] += 1
  VD[v2] += 1                   ' Obliczamy stopnie v1 i v2
Next

Close #1

Print

' Szukamy pozycji startowej v1

v1 = 0
While v1 < n
  If VD[v1] > 0 Then Exit While
  v1 += 1
Wend

For i = v1 To n - 1
  If VD[i] Mod 2 = 1 Then
    v1 = i
    Exit For
  End If
Next

' Wyznaczamy cykl lub ścieżkę Eulera

findEuler(v1)

' Wypisujemy zawartość stosu

If VD[v1] Mod 2 = 1 Then
  Print "EULERIAN PATH :";
Else
  Print "EULERIAN CYCLE :";
End If

For i = 0 To sptr - 1
  Print Using "###";S[i];
Next
Print

' Usuwamy tablice dynamiczne

For i = 0 To n - 1
  Delete [] A[i]
Next

Delete [] A
Delete [] S
Delete [] D
Delete [] VD

End
Wynik
9 14
1 4 1 6
2 3 2 5
3 4 3 5 3 7
4 5 4 6 4 7 4 8
5 6
6 7
7 8

EULERIAN CYCLE : 1 4 3 2 5 3 7 4 5 6 4 8 7 6 1
9 13
0 1 0 6
1 4 1 6 1 8
2 7 2 8
4 6 4 7
5 7 5 8
6 7
7 8

EULERIAN PATH : 4 1 0 6 1 8 2 7 4 6 7 5 8 7

 

Algorytm Hierholzera

Lepszym algorytmem znajdowania cykli Eulera jest algorytm zaproponowany przez niemieckiego matematyka Carla Hierholzera w roku 1873. Otóż zauważył on, że cykl Eulera jest sumą cykli prostych o rozłącznych krawędziach (czyli takich, które nie przechodzą przez wspólne krawędzie). Zasada działania tego algorytmu jest następująca:

 

Wybieramy wierzchołek w grafie o niezerowym stopniu wychodzącym. Od tego wierzchołka znajdujemy cykl, czyli szukamy ścieżki, która kończy się w tym samym wierzchołku. Zapamiętujemy na liście kolejne wierzchołki tej ścieżki. Wszystkie krawędzie cyklu usuwamy z grafu. Teraz, mając ten pierwszy cykl, w pętli przechodzimy jego kolejne wierzchołki. Dopóki dany wierzchołek posiada krawędzie wychodzące, znajdujemy kolejny cykl, który zawiera ten wierzchołek. Krawędzie tego nowego cyklu usuwamy z grafu, a sam cykl dołączamy do listy dwukierunkowej w miejscu bieżącego wierzchołka – w ten sposób cykl zostaje wydłużony. Pętlę kontynuujemy, a gdy zostaną znalezione wszystkie cykle w danym wierzchołku, przechodzimy do kolejnego na liście i całość powtarzamy.

 

Algorytm Hierholza pozwala znajdować cykle Eulera w grafach skierowanych i nieskierowanych. Prześledźmy sposób pracy tego algorytmu w poniższej tabelce.

 

C: Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste.
C: 0 1 2 0 Wybieramy wierzchołek startowy 0 (może być to dowolny inny wierzchołek o niezerowym stopniu wychodzącym). Znajdujemy cykl prosty rozpoczynający się w tym wierzchołku. Cykl umieszczamy na liście, a z grafu usuwamy wszystkie krawędzie tego cyklu – zapobiegnie to ponownemu wybieraniu tych krawędzi w kolejnych cyklach.
C: [0] 1 2 0
C: 0 3 1 4 0 1 2 0
Teraz przeglądamy listę cyklu C. Pierwszy wierzchołek 0 posiada wciąż krawędzie. Zatem uruchamiamy znów wyszukiwanie cyklu o początku w wierzchołku 0. Załóżmy, że będzie to cykl 0 3 1 4 0. Krawędzie cyklu usuwamy z grafu, a ze znalezionego cyklu usuwamy pierwszy wierzchołek i wstawiamy cykl na listę C za bieżącym wierzchołkiem. Otrzymamy w ten sposób cykl rozszerzony.
C: 0 [3] 1 4 0 1 2 0
C: 0 3 2 5 4 3 1 4 0 1 2 0
Po usunięciu krawędzi poprzedniego cyklu wierzchołek 0 stał się izolowanym. Na liście C przechodzimy do następnego wierzchołka, który posiada krawędzie – do wierzchołka 3. Znajdujemy nowy cykl 3 2 5 4 3 i wstawiamy go na listę C.
C: 0 3 2 5 4 3 1 4 0 1 2 0 Po tej operacji dalsze przeglądnięcie listy C nie znajdzie już wierzchołków o niezerowym stopniu. Zatem lista C zawiera cykl Eulera.
C: 0 3 2 5 4 3 1 4 0 1 2 0  

 

Algorytm Hierholzera znajdowania cyklu lub ścieżki Eulera w grafie skierowanym

Rekurencyjna funkcja DFSaddCycle(graf,v,w,p,visited)
Wejście
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
v    wierzchołek startowy
w    wierzchołek bieżący
p  –  referencja do wskaźnika elementów dwukierunkowej listy wierzchołków C
visited    tablica logiczna wierzchołków odwiedzonych
Wyjście:
true – znaleziono cykl, false – brak cyklu.

C  zawiera dodany ciąg wierzchołków, które tworzą cykl.

Elementy pomocnicze:
u    wierzchołek, u C
Lista kroków:
K01: visited[w] ← true ; ustaw wierzchołek w jako odwiedzony
K02: Za p wstaw do listy C nowy element z wierzchołkiem w ; wierzchołek w stawiamy do cyklu
K03: p ← (pnext) ; przesuń p na dodany element
K04: Dla każdego sąsiada u wierzchołka w wykonuj K05...K11 ; przeglądamy sąsiadów wierzchołka w
K05:     Jeśli uv, to idź do K11 ; jeśli sąsiad nie jest wierzchołkiem startowym cyklu, idziemy dalej
K06:     Za p wstaw do listy C nowy element z wierzchołkiem v ; znaleźliśmy cykl, do listy C wstawiamy wierzchołek startowy
K07:         Usuń krawędź (pv)–(pnextv) ; z grafu usuwamy wszystkie krawędzie cyklu
K08:         Jeśli (pv) = v, to zakończ z wynikiem true  
K09:         p ← (pprev) ; cofając się po liście wstecz w kierunku wierzchołka startowego
K10:     Idź do K07 ; powrót na początek pętli
K11:     Jeśli (visited[u] = false) (DFSaddCycle(graf,v,u,p,visited) = true),
    to zakończ z wynikiem true
; rekurencyjne wywołanie
K12: p ← (pprev) ; wierzchołek w nie należy do tego cyklu
K13: Usuń z listy C element wskazywany przez (pnext) ; usuwamy go z cyklu
K14: Zakończ z wynikiem false  

 

Algorytm główny
Wejście
n  –  liczba wierzchołków grafu, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi zawierać cykl Eulera, co można sprawdzić innym algorytmem.
Wyjście:
C – lista dwukierunkowa zawierająca kolejno odwiedzane wierzchołki w cyklu Eulera
Elementy pomocnicze:
p    wskaźniki elementów listy C
visited    n elementowa tablica logiczna odwiedzin
Lista kroków:
K01: Utwórz pustą listę C.  
K02: Utwórz n elementową tablicę visited  
K03: Wyszukaj w grafie wierzchołek v o niezerowym stopniu  
K04: Umieść v na liście C ; start cyklu
K05: Ustaw p na pierwszy element listy C  
K06: Dopóki p ≠ nil, wykonuj K07...K10 ; idziemy wzdłuż elementów listy C
K07:     Dopóki wierzchołek (pv) ma sąsiada u, wykonuj K08...K09  
K08:         Wyzeruj tablicę visited  
K09:         DFSaddCycle(n,graf,(pv),u,p,visited) ; dodajemy do C nowy cykl
K10:     p ← (pnext)  
K11: Zakończ  

 

Uwaga: wersja dla grafu nieskierowanego wymaga jedynie modyfikacji funkcji DFSfindCycle() tak, aby szukała ścieżek w grafach nieskierowanych. Odpowiedni algorytm jest przedstawiony w rozdziale o znajdowaniu cykli w grafach.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje definicję grafu skierowanego i sprawdza istnienie w nim ścieżki lub cyklu Eulera. Wynik jest wypisywany w oknie konsoli:

Przykładowe dane dla programu:

Graf z cyklem Eulera

symbol

9 17
0 1
1 3 1 4
2 1 2 5
3 0 3 2 3 7
4 2 4 3 4 6
5 4 5 7
6 3
7 4 7 8
8 5

 

Lazarus
// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program hierholzer;

// Typy danych

type
  nptr = array of byte;         // wiersz macierzy sąsiedztwa

  PdlistEl = ^dlistEl;          // Wskaźnik elementów listy dwukierunkowej
  dlistEl =  record
    next  : PdlistEl;
    prev  : PdlistEl;
    v     : integer;
  end;

// Zmienne globalne

var
  m,n : integer;                // Liczba krawędzi i wierzchołków
  graf: array of nptr;          // Dynamiczna macierz sąsiedztwa
  visited : array of boolean;   // Tablica odwiedzin

// Procedury obsługi listy dwukierunkowej
//---------------------------------------

// Procedura dołącza do listy nowy element
// za elementem wskazywanym przez p
//------------------------------------------
procedure addC(x : integer; p : PdlistEl);
var
  r : PdlistEl;
begin
  new(r);
  r^.v := x;
  r^.next := p^.next;
  if r^.next <> nil then r^.next^.prev := r;
  r^.prev := p;
  p^.next := r;
end;

// Procedura usuwa z listy element wskazywany przez p
//---------------------------------------------------
procedure remC(p : PdlistEl);
begin
  if p^.next <> nil then p^.next^.prev := p^.prev;
  if p^.prev <> nil then p^.prev^.next := p^.next;
  dispose(p);
end;

// Rekurencyjna funkcja dodająca do listy nowy cykl
// v - wierzchołek startowy i końcowy cyklu
// w - wierzchołek bieżący
// p - referencja do wskazania punktu wstawiania na liście
//--------------------------------------------------------
function DFSaddCycle(v,w : integer; var p : PdlistEl) : boolean;
var
  u : integer;
begin
  visited[w] := true;           // Oznaczamy v jako odwiedzony
  addC(w,p);                    // Dodajemy w do cyklu
  p := p^.next;                 // p wskazuje dodany element
  for u := 0 to n - 1 do        // Przeglądamy sąsiadów w
    if graf[w][u] = 1 then
    begin
      if u = v then             // Cykl znaleziony?
      begin
        addC(v,p);              // Zamykamy cykl na liście C
        repeat
          graf[p^.v][p^.next^.v] := 0; // Usuwamy krawędzie cyklu
          if p^.v = v then Exit(true);
          p := p^.prev;
        until false;
      end;
      if not visited[u] and DFSaddCycle(v,u,p) then Exit(true);
    end;
  p := p^.prev;                 // Z listy usuwamy w
  remC(p^.next);
  DFSaddCycle := false;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i,j,v1,v2 : integer;
  C   : PdlistEl;               // Lista cyklu Eulera
  p : PdlistEl;
begin
  read(n,m);                    // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength(graf,n);
  SetLength(visited,n);
  for i := 0 to n - 1 do
  begin
    SetLength(graf[i],n);
    for j := 0 to n - 1 do graf[i][j] := 0;
  end;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m - 1 do
  begin
    read(v1,v2);
    graf[v1][v2] := 1;
  end;

  new(C);                       // Tworzymy listę z wierzchołkiem v1
  C^.v := v1;
  C^.next := nil;
  C^.prev := nil;

  p := C;                       // p wskazuje pierwszy element listy
  while p <> nil do             // Przeglądamy listę C
  begin
    for i := 0 to n - 1 do      // Szukamy sąsiadów
      if graf[p^.v][i] = 1 then
      begin
        for j := 0 to n - 1 do visited[j] := false;
        DFSaddCycle(p^.v,i,p);  // Dla każdego sąsiada uruchamiamy szukanie cyklu
      end;
    p := p^.next;               // Następny element listy C
  end;

  writeln;

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  p := C;
  while p <> nil do
  begin
    write(p^.v:3);
    p := p^.next;
  end;

  writeln;

  // Usuwamy zmienne dynamiczne

  p := C;
  while p <> nil do
  begin
    p := C^.next;
    remC(C);
    C := p;
  end;

  for i := 0 to n - 1 do SetLength(graf[i],0);

  SetLength(graf,0);
  SetLength(visited,0);
end.
Code::Blocks
// Wyszukiwanie cyklu lub ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

struct dlistEl
{
  dlistEl *next,*prev;
  int v;
};

// Zmienne globalne

int m,n;                        // Liczba krawędzi i wierzchołków
char **graf;                    // Dynamiczna macierz sąsiedztwa
bool * visited;                 // Tablica odwiedzin

// Procedury obsługi listy dwukierunkowej
//---------------------------------------

// Procedura dołącza do listy nowy element
// za elementem wskazywanym przez p
//------------------------------------------
void addC(int x, dlistEl *p)
{
  dlistEl * r;

  r = new dlistEl;
  r->v = x;
  r->next = p->next;
  if(r->next) r->next->prev = r;
  r->prev = p;
  p->next = r;
}

// Procedura usuwa z listy element wskazywany przez p
//---------------------------------------------------
void remC(dlistEl *p)
{
  if(p->next) p->next->prev = p->prev;
  if(p->prev) p->prev->next = p->next;
  delete p;
}

// Rekurencyjna funkcja dodająca do listy nowy cykl
// v - wierzchołek startowy i końcowy cyklu
// w - wierzchołek bieżący
// p - referencja do wskazania punktu wstawiania na liście
//--------------------------------------------------------
bool DFSaddCycle(int v, int w, dlistEl * & p)
{
  int u;

  visited[w] = true;            // Oznaczamy v jako odwiedzony
  addC(w,p);                    // Dodajemy w do cyklu
  p = p->next;                  // p wskazuje dodany element
  for(u = 0; u < n; u++)        // Przeglądamy sąsiadów w
    if(graf[w][u])
    {
      if(u == v)                // Cykl znaleziony?
      {
        addC(v,p);              // Zamykamy cykl na liście C
        do
        {
          graf[p->v][p->next->v] = 0; // Usuwamy krawędzie cyklu
          if(p->v == v) return true;
          p = p->prev;
        } while(true);
      }
      if(!visited[u] && DFSaddCycle(v,u,p)) return true;
    }
  p = p->prev;                 // Z listy usuwamy w
  remC(p->next);
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,j,v1,v2;
  dlistEl *C,*p;

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf    = new char * [n];
  visited = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = new char [n];
    for(j = 0; j < n; j++) graf[i][j] = 0;
  }

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    graf[v1][v2] = 1;
  }

  C = new dlistEl;              // Tworzymy listę z wierzchołkiem v1
  C->v = v1;
  C->next = NULL;
  C->prev = NULL;

  for(p = C; p; p = p->next)    // Przeglądamy listę C
    for(i = 0; i < n; i++)      // Szukamy sąsiadów
      if(graf[p->v][i])
      {
        for(j = 0; j < n; j++) visited[j] = false;
        DFSaddCycle(p->v,i,p);  // Dla każdego sąsiada uruchamiamy szukanie cyklu
      }

  cout << endl;

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  for(p = C; p; p = p->next) cout << setw(3) << p->v;

  cout << endl;

  // Usuwamy zmienne dynamiczne

  p = C;
  while(p)
  {
    p = C->next;
    remC(C);
    C = p;
  }

  for(i = 0; i < n; i++) delete [] graf[i];

  delete [] graf;
  delete [] visited;

  return 0;
}
Free Basic
' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Hierholzera
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych

Type dlistEl
  Next As dlistEl Ptr
  prev As dlistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m,n       ' Liczba krawędzi i wierzchołków
Dim Shared As Byte Ptr Ptr graf ' Dynamiczna macierz sąsiedztwa
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin

' Procedury obsługi listy dwukierunkowej
'---------------------------------------

' Procedura dołącza do listy nowy element
' za elementem wskazywanym przez p
'------------------------------------------
Sub addC(ByVal x As Integer, ByVal p As dlistEl Ptr )

  Dim As dlistEl Ptr r

  r = new dlistEl
  r->v = x
  r->next = p->Next
  If r->Next Then r->next->prev = r
  r->prev = p
  p->next = r
End Sub

' Procedura usuwa z listy element wskazywany przez p
'---------------------------------------------------
Sub remC(ByVal p As dlistEl Ptr)

  If p->Next Then p->next->prev = p->prev
  If p->prev Then p->prev->next = p->Next
  Delete p
End Sub

' Rekurencyjna funkcja dodająca do listy nowy cykl
' v - wierzchołek startowy i końcowy cyklu
' w - wierzchołek bieżący
' p - referencja do wskazania punktu wstawiania na liście
'--------------------------------------------------------
Function DFSaddCycle(ByVal v As integer, ByVal w As integer, ByRef p As dlistEl Ptr) As Integer

  Dim As Integer u

  visited[w] = 1                ' Oznaczamy v jako odwiedzony
  addC(w,p)                     ' Dodajemy w do cyklu
  p = p->Next                   ' p wskazuje dodany element
  For u = 0 To n - 1            ' Przeglądamy sąsiadów w
    If graf[w][u] > 0 Then
      If u = v Then             ' Cykl znaleziony?
        addC(v,p)               ' Zamykamy cykl na liście C
        Do
          graf[p->v][p->next->v] = 0 ' Usuwamy krawędzie cyklu
          If p->v = v then return 1
          p = p->prev
        loop While 1
      End If
      If (visited[u] = 0) AndAlso (DFSaddCycle(v,u,p) = 1) Then return 1
    End If
  Next
  p = p->prev                   ' Z listy usuwamy w
  remC(p->next)
  return 0
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As integer i,j,v1,v2
Dim As dlistEl Ptr p,C

Open Cons For Input As #1

Input #1,n,m                    ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

graf    = New Byte Ptr [n]
visited = New Byte [n]
For i = 0 To n - 1
  graf[i] = New Byte [n]
  For j = 0 To n - 1: graf[i][j] = 0: Next
Next

' Odczytujemy definicje krawędzi grafu

For i = 0 To m - 1
  Input #1,v1,v2
  graf[v1][v2] = 1
Next

Close #1

C = New dlistEl                 ' Tworzymy listę z wierzchołkiem v1
C->v = v1
C->next = 0
C->prev = 0

p = C
While p                         ' Przeglądamy listę C
  For i = 0 To n - 1            ' Szukamy sąsiadów
    If graf[p->v][i] = 1 Then
      For j = 0 To n - 1: visited[j] = 0: Next
      DFSaddCycle(p->v,i,p)     ' Dla każdego sąsiada uruchamiamy szukanie cyklu
    End If
  Next
  p = p->Next
Wend

Print

' Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

p = C
while p <> 0
  Print Using "###";p->v;
  p = p->Next
Wend

Print

' Usuwamy zmienne dynamiczne

p = C
While p
  p = C->Next
  remC(C)
  C = p
Wend

For i = 0 To n - 1: Delete [] graf[i]: Next

Delete [] graf
Delete [] visited

End
Wynik
9 17
0 1
1 3 1 4
2 1 2 5
3 0 3 2 3 7
4 2 4 3 4 6
5 4 5 7
6 3
7 4 7 8
8 5

8 5 7 4 6 3 0 1 4 3 2 5 4 2 1 3 7 8

 

Zadanie dla ambitnych

  1. Zmodyfikuj podany algorytm tak, aby szukał cyklu Eulera w grafie nieskierowanym.
  2. Algorytm Hierholzera pozwala również znajdować ścieżki Eulera. W tym celu należy zlokalizować w grafie dwa wierzchołki o różnicy stopni równej na moduł jeden dla grafu skierowanego lub o nieparzystych stopniach. Następnie wierzchołki te łączymy w odpowiedni sposób krawędzią. Otrzymamy w wyniku graf z cyklem Eulera. Cykl wyznaczamy algorytmem Hierholza, po czym wyszukujemy w nim tę dodatkową krawędź, usuwamy ją, a listę cyklicznie przesuwamy tak, aby na jej początku znalazł się wierzchołek startowy ścieżki. Zaprojektuj odpowiedni algorytm.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.