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

©2025 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: ; Przeglądamy listę sąsiedztwa
     wykonuj kroki K02…K03
K02:   Usuń z grafu krawędź vu ; 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ędzi pomiędzy wierzchołkiem i-tym 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
  // Wiersz
  nptr = array of integer;

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

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

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

var
  i, j, v1, v2 : integer;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  // Tworzymy stos
  SetLength(S, m+1);
  sptr := 0;
  for i := 0 to n-1 do
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    SetLength(A[i], n);
  // 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
    // wierzchołki końcowe
    // krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    inc(A[v1][v2]);
    // Krawędź v2->v1 obecna
    inc(A[v2][v1]);
  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;
// Macierz sąsiedztwa
int ** A;
// Stos w tablicy
int * S;

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

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

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // wskaźników
  A = new int * [n];
  // Tworzymy stos
  S = new int [m+1];
  sptr = 0;
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    A[i] = new int [n];
  // 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++)
  {
    // wierzchołki końcowe
    // krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2]++;
    // Krawędź v2->v1 obecna
    A[v2][v1]++;
  }
  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
' Macierz sąsiedztwa
Dim Shared As Integer Ptr Ptr A
' Stos w tablicy
Dim Shared As Integer Ptr S

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

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

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

Dim As integer i, j, v1, v2

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New integer Ptr [n]
' Tworzymy stos
S = New Integer [m+1]
sptr = 0
For i = 0 To n-1
  ' Tworzymy wiersze
  ' macierzy sąsiedztwa
  A[i] = New Integer [n]
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
  ' wierzchołki końcowe
  ' krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] += 1
  ' Krawędź v2->v1 obecna
  A[v2][v1] += 1
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
Python (dodatek)
# Wyszukiwanie cyklu Eulera
# Data: 5.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Procedura wyszukuje cykl Eulera
# We:
# v - wierzchołek startowy
#--------------------------------
def dfs_euler(v):
    global a,n,s,sptr
    # Przeglądamy sąsiadów
    for i in range(n):
        while a[v][i]:
            # Usuwamy krawędź
            a[v][i] -= 1
            a[i][v] -= 1
            # Rekurencja
            dfs_euler(i)
    # Wierzchołek v umieszczamy
    # na stosie
    s[sptr] = v
    sptr += 1


# **********************
# *** Program główny ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = [None] * n
# Tworzymy stos
s = [0] * (m+1)
sptr = 0
for i in range(n):
    # Tworzymy wiersze
    # macierzy sąsiedztwa
    a[i] = [0] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # wierzchołki końcowe
    # krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Krawędź v1->v2 obecna
    a[v1][v2] += 1
    # Krawędź v2->v1 obecna
    a[v2][v1] += 1
print()
# Wyznaczamy
# cykl Eulera
dfs_euler(0)
# Wypisujemy
# zawartość stosu
print("EULERIAN CYCLE :",end=" ")
for i in range(sptr):
    print(s[i], end=" ")
print()
# Usuwamy
del a,s
Wynik:
6 10
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
4 5

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

do podrozdziału  do 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.
t : chwilowo przechowuje wynik wywołania rekurencyjnego; t ∈ C.

Lista kroków:

K01: D[v] ← cv ; numerujemy wierzchołek
K02: Lowcv ; wstępna wartość parametru
K03: cvcv+1 ; kolejny wierzchołek będzie miał numer o 1 większy
K04: Dla każdego sąsiada u wierzchołka v, ; przeglądamy wszystkich
     wykonuj kroki K05…K10 ; sąsiadów wierzchołka bieżącego
K05:   Jeśli u = vf, ; pomijamy ojca na drzewie rozpinającym
       to następny obieg pętli K04
K06:   Jeśli D[u] = 0, ; sąsiad nieodwiedzony?
       to idź do kroku K09
K07:   Jeśli D[u] < Low, ; odwiedzony, krawędź wtórna.
       to LowD[u] ; Modyfikujemy parametr Low
K08:   Następny obieg pętli K04
K09:   tDFSb(u,v,graf,T,D,cv) ; rekurencyjne wywołanie funkcji
K10:   Jeśli t < Low, ; modyfikujemy parametr Low
       to Lowt
K11: Jeśli (vf > -1) obrazek (Low = D[v]), ; sąsiedzi odwiedzeni.
     to oznacz krawędź vf-v jako most ; 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 ∈ 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, ; koniec cyklu lub ścieżki
     to zakończ
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: ; szukamy krawędzi, która nie jest mostem
     Dopóki v-u jest mostem i istnieje następny sąsiad, 
     wykonuj: u ← następny sąsiad
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
  // Wiersz
  nptr = array of byte;

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

// 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
  // Numerujemy wierzchołek
  D[v] := cv;
  // Wstępna wartość Low
  Low := cv;
  // Numer dla następnego
  // wierzchołka
  inc(cv);
  // Przeglądamy sąsiadów v
  for i := 0 to n-1 do
    if (A[v][i] > 0) and
       (i <> vf) then
    begin
      // Jeśli sąsiad
      // nieodwiedzony, to
      if D[i] = 0 then
      begin
        // to wywołujemy
        // rekurencyjnie DFSb()
        temp := DFSb(i, v);
        // Modyfikujemy Low
        if temp < Low then
          Low := temp;
      end
      else
        if D[i] < Low then
          Low := D[i];
    end;
  // Mamy most?
  if (vf > -1) and
     (Low = D[v]) then
  begin
    // Oznaczamy krawędź
    // vf-v jako most
    A[vf][v] := 2;
    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
  // W pętli przetwarzamy graf
  while true do
  begin
    // v umieszczamy na stosie
    S[sptr] := v;
    inc(sptr);
    // Szukamy pierwszego
    // sąsiada v
    u := 0;
    while (u < n) and
          (A[v][u] = 0) do
      inc(u);
    // Nie ma sąsiadów,
    // kończymy
    if u = n then break;
    // Zerujemy tablicę D
    for i := 0 to n-1 do
      D[i] := 0;
    // Numer pierwszego
    // wierzchołka dla DFS
    cv := 1;
    // Identyfikujemy
    // krawędzie-mosty
    DFSb(v, -1);
    // 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;
    // Usuwamy krawędź v-u
    A[v][u] := 0;
    A[u][v] := 0;
    // Przechodzimy do u
    v := u;
  end;
end;

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

var
  i, j, v1, v2 : integer;
  // Stopnie wierzchołków
  VD : array of integer;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // wskaźników
  SetLength(A, n);
  for i := 0 to n-1 do
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
    for j := 0 to n-1 do
      A[i][j] := 0;
  // Tworzymy tablicę stopni
  SetLength(VD, n);
  // Zerujemy tablicę stopni
  for i := 0 to n-1 do
    VD[i] := 0;
  // Tworzymy tablicę numerów
  SetLength(D, n);
  // Tworzymy pusty stos
  SetLength(S, m+1);
  sptr := 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    A[v1][v2] := 1;
    // Krawędź v2->v1 obecna
    A[v2][v1] := 1;
    inc(VD[v1]);
    // Obliczamy
    // stopnie v1 i v2
    inc(VD[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;
// Macierz sąsiedztwa
char **A;
// Stos w tablicy
int *S;
// Tablica numerów wierzchołków
int *D;

// 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;

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

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

  // W pętli
  // przetwarzamy graf
  while(true)
  {
    // v umieszczamy
    // na stosie
    S[sptr++] = v;
    // Szukamy pierwszego
    // sąsiada v
    for(u = 0; (u < n) &&
               !A[v][u];u++);
    // Nie ma sąsiadów,
    // kończymy
    if(u == n) break;
    for(i = 0; i < n; i++)
      // Zerujemy tablicę D
      D[i] = 0;
    // Numer pierwszego
    // wierzchołka dla DFS
    cv = 1;
    // Identyfikujemy
    // krawędzie-mosty
    DFSb(v, -1);
    // 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;
    // Usuwamy krawędź v-u
    A[v][u] = A[u][v] = 0;
    // Przechodzimy do u
    v = u;
  }
}

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

int main()
{
  int i, j, v1, v2;
  // Stopnie wierzchołków
  int * VD;
  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy
  // tablicę wskaźników
  A = new char * [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    A[i] = new char [n];
  // Macierz
  // wypełniamy zerami
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  // Tworzymy tablicę stopni
  VD = new int [n];
  // Zerujemy tablicę stopni
  for(i = 0; i < n; i++)
    VD[i] = 0;
  // Tworzymy tablicę numerów
  D = new int [n];
  // Tworzymy pusty stos
  S = new int [m+1];
  sptr = 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2] = 1;
    // Krawędź v2->v1 obecna
    A[v2][v1] = 1;
    // Obliczamy
    // stopnie v1 i v2
    VD[v1]++;
    VD[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
' Macierz sąsiedztwa
Dim Shared As Byte Ptr Ptr  A
' Stos w tablicy
Dim Shared As Integer Ptr S
' Tablica numerów wierzchołków
Dim Shared As Integer Ptr D

' 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

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

  ' W pętli przetwarzamy graf
  While 1
    ' v umieszczamy na stosie
    S[sptr] = v
    sptr += 1
    u = 0
    ' Szukamy pierwszego sąsiada v
    While (u < n) AndAlso _
          (A[v][u] = 0)
      u += 1
    Wend
    ' Nie ma sąsiadów, kończymy
    If u = n Then Exit While
    For i = 0 To n-1
      ' Zerujemy tablicę D
      D[i] = 0
    Next
    ' Numer pierwszego
    ' wierzchołka dla DFS
    cv = 1
    ' Identyfikujemy krawędzie-mosty
    DFSb(v, -1)
    ' 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
    ' Usuwamy krawędź v-u
    A[v][u] = 0: A[u][v] = 0
    ' Przechodzimy do u
    v = u
  Wend
End Sub

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

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

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  ' macierzy sąsiedztwa
  A[i] = New Byte [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  For j = 0 To n-1
    A[i][j] = 0
  Next
Next
' Tworzymy tablicę stopni
VD = New integer [n]
' Zerujemy tablicę stopni
For i = 0 To n-1
  VD[i] = 0
Next
' Tworzymy tablicę numerów
D = New integer [n]
' Tworzymy pusty stos
S = New integer [m+1]
sptr = 0
' Odczytujemy kolejne
' definicje krawędzi
For i = 0 To m-1
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] = 1
  ' Krawędź v2->v1 obecna
  A[v2][v1] = 1
  ' Obliczamy stopnie v1 i v2
  VD[v1] += 1
  VD[v2] += 1
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
Python (dodatek)
# Wyszukiwanie cyklu
# lub ścieżki Eulera
# Algorytm Fleury#ego
# Data: 6.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# 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
#---------------------------------
def dfs_b(v, vf):
    global d,cv,a,n
    # Numerujemy wierzchołek
    d[v] = cv
    # Wstępna wartość Low
    low = cv
    # Numer dla następnego
    # wierzchołka
    cv += 1
    # Przeglądamy sąsiadów v
    for i in range(n):
        if (a[v][i] > 0) and (i != vf):
           # Jeśli sąsiad
           # nieodwiedzony, to
           if not d[i]:
              # to wywołujemy
              # rekurencyjnie DFSb()
              temp = dfs_b(i, v)
              # Modyfikujemy Low
              if temp < low:
                 low = temp
           else:
              if d[i] < low:
                 low = d[i]
    # Mamy most?
    if (vf > -1) and (low == d[v]):
        # Oznaczamy krawędź
        # vf-v jako most
        a[vf][v] = 2
        a[v][vf] = 2
    return low


# Procedura wyszukuje
# cykl lub ścieżkę Eulera
# We:
# v - wierzchołek startowy
#-------------------------
def find_euler(v):
    global s,sptr,a,n,cv,d
    # W pętli przetwarzamy graf
    while True:
       # v umieszczamy na stosie
       s[sptr] = v
       sptr += 1
       u = 0
       # Szukamy pierwszego sąsiada v
       while (u < n) and not a[v][u]:
          u += 1
       # Nie ma sąsiadów, kończymy
       if u == n: break
       # Zerujemy tablicę D
       d = [0] * n
       # Numer pierwszego
       # wierzchołka dla DFS
       cv = 1
       # Identyfikujemy krawędzie-mosty
       dfs_b(v, -1)
       # Szukamy krawędzi
       # nie będącej mostem
       w = u+1
       while (a[v][u] == 2) and (w < n):
          if a[v][w] > 0:
              u = w
          w += 1
       # Usuwamy krawędź v-u
       a[v][u] = 0
       a[u][v] = 0
       # Przechodzimy do u
       v = u


# **********************
# *** Program główny ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = [None] * n
for i in range(n):
    # Tworzymy wiersze
    # macierzy sąsiedztwa
    a[i] = [0] * n
# Tworzymy tablicę stopni
vd = [0] * n
# Tworzymy tablicę numerów
d = [0] * n
# Tworzymy pusty stos
s = [0] * (m+1)
sptr = 0
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Krawędź v1->v2 obecna
    a[v1][v2] = 1
    # Krawędź v2->v1 obecna
    a[v2][v1] = 1
    # Obliczamy stopnie v1 i v2
    vd[v1] += 1
    vd[v2] += 1
print()
# Szukamy pozycji startowej v1
v1 = 0
while v1 < n:
    if vd[v1] > 0: break
    v1 += 1
for i in range(v1,n):
    if vd[i] % 2:
       v1 = i
       break
cv = 1
# Wyznaczamy cykl lub ścieżkę Eulera
find_euler(v1)
# Wypisujemy zawartość stosu
if vd[v1] % 2:
    print("EULERIAN PATH :", end=" ")
else:
    print("EULERIAN CYCLE :", end=" ")
for i in range(sptr):
    print("%3d" % s[i], end="")
print()
# Usuwamy tablice dynamiczne
del a, s, d, vd
Wynik:
9 14
1 4
1 6
2 3
2 5
3 4
3 5
3 7
4 5
4 6
4 7
4 8
5 6
6 7
7 8

EULERIAN CYCLE : 1 4 3 2 5 3 7 4 5 6 4 8 7 6 1
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

do podrozdziału  do 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 DFSac(graf,v,w,p,vs)

Wejście:

graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : wierzchołek startowy; v ∈ C.
w : wierzchołek bieżący; w ∈ C.
p : referencja do wskaźnika elementów dwukierunkowej listy wierzchołków C.
vs : tablica logiczna wierzchołków odwiedzonych.

Wyjście:

true – znaleziono cykl; false – brak cyklu.
C – lista zawierająca dodany ciąg wierzchołków, które tworzą cykl.

Elementy pomocnicze:

u : wierzchołek; u ∈ C.

Lista kroków:

K01: vs[w] ← true ; ustaw wierzchołek w jako odwiedzony
K02: Za p wstaw do listy C ; wierzchołek w stawiamy do cyklu
     nowy element z wierzchołkiem w
K03: ppnext ; przesuń p na dodany element
K04: Dla każdego sąsiada u wierzchołka w: ; przeglądamy
     wykonuj kroki K05…K11 ; sąsiadów wierzchołka w
K05:   Jeśli uv, ; jeśli sąsiad nie jest wierzchołkiem
       to idź do kroku K11 ; startowym cyklu, idziemy dalej
K06:   Za p wstaw do listy C ; znaleźliśmy cykl, do listy C
       nowy element z wierzchołkiem v ; 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:   ppprev ; 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 (vs[u] = false) obrazek ; rekurencyjne wywołanie
             (DFSac(graf,v,u,p,vs) = true), 
       to zakończ z wynikiem true
K12: ppprev ; wierzchołek w nie należy do tego cyklu
K13: Usuń z listy C element ; usuwamy go z cyklu
     wskazywany przez pnext
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:

– lista dwukierunkowa zawierająca kolejno odwiedzane wierzchołki w cyklu Eulera.

Elementy pomocnicze:

p : wskaźniki elementów listy C.
vs : n elementowa tablica logiczna odwiedzin.

Lista kroków:

K01: Utwórz pustą listę C
K02: Utwórz n elementową tablicę vs
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 pnil, ; idziemy wzdłuż elementów listy C
     wykonuj kroki K07…K10
K07: Dopóki wierzchołek pv ma sąsiada u, 
     wykonuj kroki K08…K09
K08:   Wyzeruj tablicę vs
K09:   DFSac(n,graf,pv,u,p,vs) ; dodajemy do C nowy cykl
K10:   ppnext ; idziemy wzdłuż elementów listy C
K11: Zakończ

Uwaga: wersja dla grafu nieskierowanego wymaga jedynie modyfikacji funkcji FCycle( ), 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
  // wiersz macierzy sąsiedztwa
  nptr = array of byte;

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

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

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

// Procedura dołącza do listy
// nowy element za elementem
// wskazywanym przez p
//---------------------------
procedure addC(x : integer;
               p : PDLel);
var
  r : PDLel;
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 : PDLel);
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 : PDLel)
                          : boolean;
var
  u : integer;
begin
  // Oznaczamy v jako odwiedzony
  vs[w] := true;
  // Dodajemy w do cyklu
  addC(w, p);
  // p wskazuje dodany element
  p := p^.next;
  // Przeglądamy sąsiadów w
  for u := 0 to n-1 do
    if graf[w][u] = 1 then
    begin
      // Cykl znaleziony?
      if u = v then
      begin
        // Zamykamy cykl na liście C
        addC(v, p);
        repeat
          // Usuwamy krawędzie cyklu
          graf[p^.v][p^.next^.v] := 0;
          if p^.v = v then Exit(true);
          p := p^.prev;
        until false;
      end;
      if not vs[u] and
         DFSaddCycle(v, u, p) then
        Exit(true);
    end;
  // Z listy usuwamy w
  p := p^.prev;
  remC(p^.next);
  DFSaddCycle := false;
end;

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

var
  i, j, v1, v2 : integer;
  // Lista cyklu Eulera
  C : PDLel;
  p : PDLel;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(vs, 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;
  // Tworzymy listę
  // z wierzchołkiem v1
  new(c);
  C^.v := v1;
  C^.next := nil;
  C^.prev := nil;
  // p wskazuje pierwszy
  // element listy
  p := C;
  // Przeglądamy listę C
  while p <> nil do
  begin
    // Szukamy sąsiadów
    for i := 0 to n-1 do
      if graf[p^.v][i] = 1 then
      begin
        for j := 0 to n-1 do
          vs[j] := false;
        // Dla każdego sąsiada
        // uruchamiamy szukanie
        // cyklu
        DFSaddCycle(p^.v, i, p);
      end;
    // Następny element listy C
    p := p^.next;
  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(vs, 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 DLel
{
  DLel *next, *prev;
  int v;
};

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

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

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

  r = new DLel;
  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(DLel *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,
                 DLel * & p)
{
  int u;

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

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

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

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new char * [n];
  vs = 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;
  }
  // Tworzymy listę
  // z wierzchołkiem v1
  C = new DLel;
  C->v = v1;
  C->next = nullptr;
  C->prev = nullptr;
  // Przeglądamy listę C
  for(p = C; p; p = p->next)
    // Szukamy sąsiadów
    for(i = 0; i < n; i++)
      if(graf[p->v][i])
      {
        for(j = 0; j < n; j++)
          vs[j] = false;
        // Dla każdego sąsiada
        // uruchamiamy szukanie
        // cyklu
        DFSaddCycle(p->v, i, p);
      }
  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 [] vs;
  return 0;
}
Basic
' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Hierholzera
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type DLel
  Next As DLel Ptr
  prev As DLel Ptr
  v As Integer
End Type

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

' 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 DLel Ptr)
  Dim As DLel Ptr r

  r = new DLel
  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 DLel 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 DLel Ptr) _
                             As Integer
  Dim As Integer u

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

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New Byte Ptr [n]
vs = 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
' Tworzymy listę z wierzchołkiem v1
C = New DLel
C->v = v1
C->next = 0
C->prev = 0
p = C
' Przeglądamy listę C
While p
  ' Szukamy sąsiadów
  For i = 0 To n-1
    If graf[p->v][i] = 1 Then
      For j = 0 To n-1
        vs[j] = 0
      Next
      ' Dla każdego sąsiada
      ' uruchamiamy szukanie cyklu
      DFSaddCycle(p->v, i, p)
    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 [] vs
End
Python (dodatek)
# Wyszukiwanie cyklu lub ścieżki Eulera
# Algorytm Hierholzera
# Data: 10.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy
class DLel:
    def __init__(self):
        self.next = None
        self.prev = None
        self.v = 0


# Procedury obsługi listy dwukierunkowej
#---------------------------------------
# Dołącza do listy nowy element
# za elementem wskazywanym przez p
def addc(x, p):
    r = DLel()
    r.v = x
    r.next = p.next
    if r.next:
        r.next.prev = r
    r.prev = p
    p.next = r


# Usuwa z listy element
# wskazywany przez p
def  remc(p):
    if p.next:
        p.next.prev = p.prev
    if p.prev:
        p.prev.next = p.next
    del 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
#-----------------------------------------
def dfs_add_cycle(v ,w ,p):
    global vs,n,graf
    # Oznaczamy v jako odwiedzony
    vs[w] = True
    # Dodajemy w do cyklu
    addc(w, p)
    # p wskazuje dodany element
    p = p.next
    # Przeglądamy sąsiadów w
    for u in range(n):
        if graf[w][u] > 0:
            # Cykl znaleziony?
            if u == v:
                # Zamykamy cykl na liście C
                addc(v, p)
                while True:
                    # Usuwamy
                    # krawędzie cyklu
                    graf[p.v][p.next.v] = 0
                    if p.v == v:
                        return True
                    p = p.prev
            if not vs[u] and \
               dfs_add_cycle(v,u,p):
                return True
    # Z listy usuwamy w
    p = p.prev
    remc(p.next)
    return False


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
vs = [False] * n
for i in range(n):
    graf[i] = [0] * n
# Odczytujemy definicje krawędzi grafu
for i in range(m):
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    graf[v1][v2] = 1
# Tworzymy listę z wierzchołkiem v1
c = DLel()
c.v = v1
p = c
# Przeglądamy listę C
while p:
    # Szukamy sąsiadów
    for i in range(n):
        if graf[p.v][i] == 1:
            for j in range(n):
                vs[j] = False
            # Dla każdego sąsiada
            # uruchamiamy szukanie cyklu
            dfs_add_cycle(p.v, i, p)
    p = p.next
print()
# Wyświetlamy zawartość listy C,
# czyli pełny cykl Eulera
p = c
while p:
    print("%3d" % p.v, end="")
    p = p.next
print()
# Usuwamy zmienne dynamiczne
p = c
while p:
    p = c.next
    remc(c)
    c = p
for i in range(n):
    graf[i] = None
del graf, vs
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.

do podrozdziału  do strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2025 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.