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

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Znajdowanie cyklu lub ścieżki Eulera

SPIS TREŚCI
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 a i, 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.
Zmienne 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.
Zmienne 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.
Zmienne 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
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ź ( 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 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  ← ( 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.
Zmienne 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 ( pv  ) ma sąsiada u,
    wykonuj kroki 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.


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
©2021 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.