Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Znajdowanie cyklu lub ścieżki Eulera

SPIS TREŚCI W KONSERWACJI
Podrozdziały

Problem

W danym grafie należy 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
kroki 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 podejście umożliwia szukanie cykli Eulera w multigrafach.


Przykładowe programy

Uwaga:

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.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
Graf z cyklem Eulera
obrazek
6 10
0 4 0 5
1 2 1 3 1 4 1 5
2 3 2 4 2 5
4 5
Pascal
// 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.
C++
// 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;}
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:
xxx6 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
obrazek

Na początek:  podrozdziału   strony 

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:

obrazek S: Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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ź.
obrazek 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.
obrazek 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ź.
obrazek 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.
obrazek 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.
obrazek 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ź.
obrazek 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ź.
obrazek 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
kroki 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 kroku K09
sąsiad nieodwiedzony?
K07: Jeśli D [u] < Low,
to Low ← D [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 Low ← temp
modyfikujemy parametr Low
K11: Jeśli (vf > -1) obrazek (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 v ← u przechodzimy do wierzchołka u
K12: Idź do kroku 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.

Przykładowe programy

Uwaga:

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.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
Graf z cyklem Eulera
obrazek
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
obrazek
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
Pascal
// 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.
C++
// 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;}
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:
xxx9 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
obrazek
   
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
obrazek

Na początek:  podrozdziału   strony 

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.

obrazek C: Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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 ← (p→next) przesuń p na dodany element
K04: Dla każdego sąsiada u wierzchołka w :
wykonuj
kroki K05…K11
przeglądamy sąsiadów wierzchołka w
K05: Jeśli u ≠ v,
to idź do kroku 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ź (p→v) – (p→next→v) z grafu usuwamy wszystkie krawędzie cyklu
K08: Jeśli (p→v) = v,
to zakończ z wynikiem true
 
K09: p ← (p→prev) cofając się po liście wstecz w kierunku wierzchołka startowego
K10: Idź do kroku K07 powrót na początek pętli
K11: Jeśli ( visited [u] = false) obrazek (DFSaddCycle (graf, v, u, p, visited) = true),
to zakończ z wynikiem true
rekurencyjne wywołanie
K12: p ← (p→prev) wierzchołek w nie należy do tego cyklu
K13: Usuń z listy C element
wskazywany przez (p→next)
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 kroki K07…K10
idziemy wzdłuż elementów listy C
K07: Dopóki wierzchołek (p→v) ma sąsiada u,
wykonuj kroki K08…K09
 
K08: Wyzeruj tablicę visited  
K09: DFSaddCycle (n, graf, (p→v), u, p, visited) dodajemy do C nowy cykl
K10: p ← ( p→next)  
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.


Przykładowe programy

Uwaga:

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:
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
Graf z cyklem Eulera
obrazek
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
Pascal
// 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.
C++
// 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;}
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
obrazek

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.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.