Serwis Edukacyjny w I-LO w Tarnowie ![]() 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 |
ProblemW 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. |
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.
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ź 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
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. |
Graf z cyklem Eulera![]() |
6 10 0 4 0 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 4 5 |
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. |
// 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 |
![]() |
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:
Aby lepiej zrozumieć zasadę działania algorytmu Fleury'ego, prześledźmy kolejne operacje:
![]() |
S: | Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste. |
![]() |
S: 0 | Jako punkt startowy możemy wybrać dowolny wierzchołek o stopniu niezerowym. Wybierzmy zatem wierzchołek 0 i wpiszmy go na stos, który będzie zawierał kolejno odwiedzane wierzchołki w cyklu. Z wierzchołka 0 prowadzą dwie krawędzie do wierzchołków 4 i 5. Żadna nie jest mostem, zatem możemy wybrać dowolną z nich. Wybieramy krawędź prowadzącą do wierzchołka 4, przechodzimy do tego wierzchołka, a krawędź usuwamy. |
![]() |
S: 4 0 | Jesteśmy w wierzchołku 4. Umieszczamy go na stosie. W wierzchołku 4 mamy krawędzie do wierzchołków 1, 2 i 5 (krawędź do 0 została usunięta!). Żadna z nich nie jest mostem, zatem wybieramy krawędź do wierzchołka 1, przechodzimy do niego i krawędź usuwamy. |
![]() |
S: 1 4 0 | Wierzchołek 1 umieszczamy na stosie. Żadna z krawędzi do wierzchołków 2, 3 i 5 nie jest mostem. Wybieramy krawędź do wierzchołka 2, przechodzimy do wierzchołka 2, a krawędź usuwamy z grafu. |
![]() |
S: 2 1 4 0 | Wierzchołek 2 dopisujemy do stosu. Krawędzie do wierzchołków 3, 4 i 5 nie są mostami. Wybieramy krawędź do wierzchołka 3, przechodzimy do niego i usuwamy przebytą krawędź. |
![]() |
S: 3 2 1 4 0 | Wierzchołek 3 dopisujemy do stosu. W wierzchołku 3 pozostała tylko krawędź do wierzchołka 1. Jest ona mostem, lecz nie mamy innego wyboru. Idziemy zatem do wierzchołka 1, a krawędź usuwamy. |
![]() |
S: 1 3 2 1 4 0 | Wierzchołek 1 dopisujemy do stosu. Krawędź do wierzchołka 5 również jest mostem, ale nie mamy innego wyboru. Idziemy do wierzchołka 5 i usuwamy krawędź. |
![]() |
S: 5 1 3 2 1 4 0 | Wierzchołek 5 dopisujemy do stosu. Krawędź do wierzchołka 0 jest mostem, tej nie możemy wybrać, ponieważ mamy też inne krawędzie, które nie są mostami: do wierzchołków 2 i 4. Wybieramy krawędź do wierzchołka 2, przechodzimy do niego, krawędź usuwamy z grafu. |
![]() |
S: 2 5 1 3 2 1 4 0 | Wierzchołek 2 dopisujemy do stosu. Pozostała nam tylko krawędź do wierzchołka 4. Przechodzimy do niego, krawędź usuwamy. |
![]() |
S: 4 2 5 1 3 2 1 4 0 | Wierzchołek 4 dopisujemy do stosu, przechodzimy do wierzchołka 5 i usuwamy krawędź. |
![]() |
S: 5 4 2 5 1 3 2 1 4 0 | Wierzchołek 5 dopisujemy do stosu, przechodzimy do wierzchołka 0 i usuwamy krawędź. |
![]() |
S: 0 5 4 2 5 1 3 2 1 4 0 | Wierzchołek 0 dopisujemy do stosu. Ponieważ nie ma już dalszych krawędzi, algorytm kończymy. Na stosie zapisany jest ciąg wierzchołków cyklu Eulera w odwrotnej kolejności odwiedzin (dla grafu nieskierowanego zwrot cyklu Eulera nie ma znaczenia). |
Algorytm Fleury'ego jest elegancki i łatwy do zrozumienia, jednakże niezbyt efektywny, ponieważ wymaga wyznaczania mostów w każdym odwiedzanym wierzchołku (wyznaczanie mostów możemy pominąć, jeśli wierzchołek ma tylko jednego sąsiada – do wyznaczania tych mostów można użyć podanego wcześniej algorytmu Tarjana, który działa w czasie liniowym).
Ten sam algorytm Fleury'ego można zastosować do znajdowania ścieżki Eulera. W tym przypadku rozpoczynamy w węźle o nieparzystym stopniu. Reszta jest identyczna jak dla cyklu Eulera.
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, ; 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 Low ← D[u] ; Modyfikujemy parametr Low K08: Następny obieg pętli K04 K09: t ← DFSb(u,v,graf,T,D,cv) ; rekurencyjne wywołanie funkcji K10: Jeśli t < Low, ; modyfikujemy parametr Low to Low ← t K11: Jeśli (vf > -1)(Low = D[v]), ; sąsiedzi odwiedzeni. to oznacz krawędź vf-v jako most ; Sprawdzamy warunek mostu K12: Zakończ z wynikiem Low
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:
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. |
Graf z cyklem Eulera![]() |
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![]() |
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 |
![]() |
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 |
![]() |
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:
Algorytm Hierholza pozwala znajdować cykle Eulera w grafach skierowanych i nieskierowanych. Prześledźmy sposób pracy tego algorytmu w poniższej tabelce.
![]() |
C: | Mamy dany graf nieskierowany, który zawiera cykl Eulera, ponieważ jest spójny i wszystkie wierzchołki posiadają stopnie parzyste. |
![]() |
C: 0 1 2 0 | Wybieramy wierzchołek startowy 0 (może być to dowolny inny wierzchołek o niezerowym stopniu wychodzącym). Znajdujemy cykl prosty rozpoczynający się w tym wierzchołku. Cykl umieszczamy na liście, a z grafu usuwamy wszystkie krawędzie tego cyklu – zapobiegnie to ponownemu wybieraniu tych krawędzi w kolejnych cyklach. |
![]() |
C: [0] 1 2 0 C: 0 3 1 4 0 1 2 0 |
Teraz przeglądamy listę cyklu C. Pierwszy wierzchołek 0 posiada wciąż krawędzie. Zatem uruchamiamy znów wyszukiwanie cyklu o początku w wierzchołku 0. Załóżmy, że będzie to cykl 0 3 1 4 0. Krawędzie cyklu usuwamy z grafu, a ze znalezionego cyklu usuwamy pierwszy wierzchołek i wstawiamy cykl na listę C za bieżącym wierzchołkiem. Otrzymamy w ten sposób cykl rozszerzony. |
![]() |
C: 0 [3] 1 4 0 1 2 0 C: 0 3 2 5 4 3 1 4 0 1 2 0 |
Po usunięciu krawędzi poprzedniego cyklu wierzchołek 0 stał się izolowanym. Na liście C przechodzimy do następnego wierzchołka, który posiada krawędzie – do wierzchołka 3. Znajdujemy nowy cykl 3 2 5 4 3 i wstawiamy go na listę C. |
![]() |
C: 0 3 2 5 4 3 1 4 0 1 2 0 | Po tej operacji dalsze przeglądnięcie listy
C nie znajdzie już wierzchołków o niezerowym stopniu. Zatem lista C zawiera cykl Eulera. |
![]() |
C: 0 3 2 5 4 3 1 4 0 1 2 0 |
K01:vs [w ] ← true ; ustaw wierzchołek w jako odwiedzony K02: Zap wstaw do listyC ; wierzchołek w stawiamy do cyklu nowy element z wierzchołkiemw K03:p ←p →next ; przesuń p na dodany element K04: Dla każdego sąsiadau wierzchołkaw : ; przeglądamy wykonuj kroki K05…K11 ; sąsiadów wierzchołka w K05: Jeśliu ≠v , ; jeśli sąsiad nie jest wierzchołkiem to idź do kroku K11 ; startowym cyklu, idziemy dalej K06: Zap wstaw do listyC ; znaleźliśmy cykl, do listy C nowy element z wierzchołkiemv ; wstawiamy wierzchołek ; startowy K07: Usuń krawędźp →v :p →next →v ; z grafu usuwamy ; wszystkie krawędzie cyklu K08: Jeślip →v =v , to zakończ z wynikiem true K09:p ←p →prev ; cofając się po liście wstecz w kierunku ; wierzchołka startowego K10: Idź do kroku K07 ; powrót na początek pętli K11: Jeśli (vs [u ] = false); rekurencyjne wywołanie (DFSac(
graf ,v ,u ,p ,vs ) = true), to zakończ z wynikiem true K12:p ←p →prev ; wierzchołek w nie należy do tego cyklu K13: Usuń z listyC element ; usuwamy go z cyklu wskazywany przezp →next K14: Zakończ z wynikiem false
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 p ≠ nil, ; idziemy wzdłuż elementów listy C wykonuj kroki K07…K10 K07: Dopóki wierzchołek p→v ma sąsiada u, wykonuj kroki K08…K09 K08: Wyzeruj tablicę vs K09: DFSac(n,graf,p→v,u,p,vs) ; dodajemy do C nowy cykl K10: p ← p→next ; idziemy wzdłuż elementów listy C K11: Zakończ
Uwaga: wersja dla grafu nieskierowanego wymaga jedynie
modyfikacji funkcji
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: |
Graf z cyklem Eulera ![]() |
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. |
// 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 |
![]() |
![]() |
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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.