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 |
©2023 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.
graf – zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. v – numer wierzchołka grafu, v ∈ C. S – stos wierzchołków.
S - zawierająca numery kolejnych wierzchołków w jednym z cykli Eulera.
K01: Dla każdego sąsiada u wierzchołka v :
wykonuj kroki K02...K03Przeglądamy listę sąsiedztwa K02: Usuń z grafu krawędź v–u Każdą krawędź usuwamy, aby nie była wykorzystana dwukrotnie K03: DFSEuler ( graf, u, S ) Rekurencyjnie wywołujemy procedurę DFS K04: S.push ( v ) Po przetworzeniu, wierzchołek umieszczamy na stosie K05: Zakończ
Uwaga: algorytm wymaga usuwania krawędzi z grafu. Najprostszym rozwiązaniem jest tutaj zastosowanie macierzy sąsiedztwa, w której element a i, j określa liczbę krawędzie pomiędzy wierzchołkiem i-tym a j-tym. Takie podejście umożliwia szukanie cykli Eulera w multigrafach.
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 ):
|
Pascal// Wyszukiwanie cyklu Eulera // Data: 19.03.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program EulerCycle; // Typy dla dynamicznej macierzy sąsiedztwa type nptr = array of integer; // Wiersz // Zmienne globalne var n, m, sptr : integer; A : array of nptr; // Macierz sąsiedztwa S : array of integer; // Stos w tablicy // Procedura wyszukuje cykl Eulera // We: // v - wierzchołek startowy //-------------------------------- procedure DFSEuler ( v : integer ); var i : integer; begin for i := 0 to n - 1 do // Przeglądamy sąsiadów while A [ v ][ i ] > 0 do begin dec ( A [ v ][ i ] ); // Usuwamy krawędź dec ( A [ i ][ v ] ); DFSEuler ( i ); // Rekurencja end; S [ sptr ] := v; // Wierzchołek v umieszczamy na stosie inc ( sptr ); end; // ********************** // *** Program główny *** // ********************** var i, j, v1, v2 : integer; begin read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi SetLength ( A, n ); // Tworzymy tablicę wskaźników SetLength ( S, m+1 ); // Tworzymy stos sptr := 0; for i := 0 to n - 1 do SetLength ( A [ i ], n ); // Tworzymy wiersze macierzy sąsiedztwa // Macierz wypełniamy zerami for i := 0 to n - 1 do for j := 0 to n - 1 do A [ i ][ j ] := 0; // Odczytujemy kolejne definicje krawędzi for i := 1 to m do begin read ( v1, v2 ); // wierzchołki końcowe krawędzi inc ( A [ v1 ][ v2 ] ); // Krawędź v1->v2 obecna inc ( A [ v2 ][ v1 ] ); // Krawędź v2->v1 obecna end; writeln; // Wyznaczamy cykl Eulera DFSEuler ( 0 ); // Wypisujemy zawartość stosu write ( 'EULERIAN CYCLE : ' ); for i := 0 to sptr - 1 do write ( S [ i ], ' ' ); writeln; // Usuwamy tablice dynamiczne for i := 0 to n - 1 do SetLength ( A [ i ], 0 ); SetLength ( A, 0 ); SetLength ( S, 0 ); end. |
C++// Wyszukiwanie cyklu Eulera // Data: 19.03.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; // Zmienne globalne int n, m, sptr; int ** A; // Macierz sąsiedztwa int * S; // Stos w tablicy // Procedura wyszukuje cykl Eulera // We: // v - wierzchołek startowy //-------------------------------- void DFSEuler ( int v ) { int i; for( i = 0; i < n; i++ ) // Przeglądamy sąsiadów while( A [ v ][ i ] ) { A [ v ][ i ] --; // Usuwamy krawędź A [ i ][ v ] --; DFSEuler ( i ); // Rekurencja } S [ sptr++ ] = v; // Wierzchołek v umieszczamy na stosie } // ********************** // *** Program główny *** // ********************** int main( ) { int i, j, v1, v2; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new int * [ n ]; // Tworzymy tablicę wskaźników S = new int [ m + 1 ]; // Tworzymy stos sptr = 0; for( i = 0; i < n; i++ ) A [ i ] = new int [ n ]; // Tworzymy wiersze macierzy sąsiedztwa // Macierz wypełniamy zerami for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) A [ i ][ j ] = 0; // Odczytujemy kolejne definicje krawędzi for( i = 0; i < m; i++ ) { cin >> v1 >> v2; // wierzchołki końcowe krawędzi A [ v1 ][ v2 ] ++; // Krawędź v1->v2 obecna A [ v2 ][ v1 ] ++; // Krawędź v2->v1 obecna } cout << endl; // Wyznaczamy cykl Eulera DFSEuler ( 0 ); // Wypisujemy zawartość stosu cout << "EULERIAN CYCLE : "; for( i = 0; i < sptr; i++ ) cout << S [ i ] << " "; cout << endl; // Usuwamy tablice dynamiczne for( i = 0; i < n; i++ ) delete [ ] A [ i ]; delete [ ] A; delete [ ] S; return 0; } |
Basic' Wyszukiwanie cyklu Eulera ' Data: 19.03.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Zmienne globalne Dim Shared As Integer n, m, sptr Dim Shared As Integer Ptr Ptr A ' Macierz sąsiedztwa Dim Shared As Integer Ptr S ' Stos w tablicy ' Procedura wyszukuje cykl Eulera ' We: ' v - wierzchołek startowy '-------------------------------- Sub DFSEuler ( byval v As Integer ) Dim As Integer i For i = 0 To n - 1 ' Przeglądamy sąsiadów While A [ v ][ i ] A [ v ][ i ] -= 1 ' Usuwamy krawędź A [ i ][ v ] -= 1 DFSEuler ( i ) ' Rekurencja Wend Next S [ sptr ] = v ' Wierzchołek v umieszczamy na stosie sptr += 1 End Sub ' ********************** ' *** Program główny *** ' ********************** Dim As integer i, j, v1, v2 Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New integer Ptr [ n ] ' Tworzymy tablicę wskaźników S = New Integer [ m + 1 ] ' Tworzymy stos sptr = 0 For i = 0 To n - 1 A [ i ] = New Integer [ n ] ' Tworzymy wiersze macierzy sąsiedztwa Next ' Macierz wypełniamy zerami For i = 0 To n - 1 For j = 0 To n - 1 A [ i ][ j ] = 0 Next Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m - 1 Input #1, v1, v2 ' wierzchołki końcowe krawędzi A [ v1 ][ v2 ] += 1 ' Krawędź v1->v2 obecna A [ v2 ][ v1 ] += 1 ' Krawędź v2->v1 obecna Next Print Close #1 ' Wyznaczamy cykl Eulera DFSEuler ( 0 ) ' Wypisujemy zawartość stosu Print "EULERIAN CYCLE :"; For i = 0 To sptr - 1 Print S [ i ]; Next Print ' Usuwamy tablice dynamiczne For i = 0 To n - 1 Delete [ ] A [ i ] Next Delete [ ] A Delete [ ] S End |
Wynik: | |
xxx6 10 0 4 0 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 4 5 EULERIAN CYCLE : 0 5 4 2 5 1 3 2 1 4 0 |
![]() |
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.
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. |
Low | – | wartość parametru Low dla bieżącego wierzchołka, Low ∈ C. |
temp | – | chwilowo przechowuje wynik wywołania rekurencyjnego, t ∈ C. |
K01: | D [ v ] ← cv | numerujemy wierzchołek |
K02 | Low ← cv | wstępna wartość parametru |
K03: | cv ← cv + 1 | kolejny wierzchołek będzie miał numer o 1 większy |
K04: | Dla każdego sąsiada u
wierzchołka
v, wykonuj kroki K05...K10 |
przeglądamy wszystkich sąsiadów wierzchołka bieżącego |
K05: | Jeśli u
= vf, to następny obieg pętli K04 |
pomijamy ojca na drzewie rozpinającym |
K06: | Jeśli D
[ u ] = 0, to idź do kroku K09 |
sąsiad nieodwiedzony? |
K07: | Jeśli D
[ u ] < Low, to Low ← D [ u ] |
odwiedzony, krawędź wtórna. Modyfikujemy parametr Low |
K08: | Następny obieg pętli K04 | |
K09: | temp ← DFSb ( u, v, graf, T, D, cv ) | rekurencyjne wywołanie funkcji |
K10: | Jeśli temp
<
Low, to Low ← temp |
modyfikujemy parametr Low |
K11: | Jeśli ( vf > -1 )
![]() to oznacz krawędź vf-v jako most |
sąsiedzi odwiedzeni. Sprawdzamy warunek mostu |
K12: | Zakończ z wynikiem Low |
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. |
S | – | stos zawiera kolejno odwiedzone wierzchołki cyklu lub ścieżki Eulera. |
cv | – | przechowuje numery wierzchołków dla DFS, cv ∈ C. |
D | – | dynamiczna tablica dla numerów wierzchołków nadawanych przez DFS. Elementy są liczbami całkowitymi. |
u | – | numer wierzchołka w grafie, u, w ∈ C. |
K01: | Utwórz n elementową tablicę D | |
K02: | Utwórz pusty stos S | |
K03: | S.push ( v ) | wierzchołek v na stos |
K04: | Jeśli v nie ma
sąsiadów, to zakończ |
koniec cyklu lub ścieżki |
K05: | u ← pierwszy sąsiad v | |
K06: | Wyzeruj tablicę D | inaczej musimy wyszukać mosty |
K07: | cv ← 1 | |
K08: | DFSb ( v, -1, graf, D, cv ) | szukamy mostów |
K09: | Dopóki v-u
jest mostem i istnieje następny sąsiad, wykonuj: u ← następny sąsiad |
szukamy krawędzi, która nie jest mostem |
K10: | Usuń krawędź v-u z grafu | przebytą krawędź usuwamy |
K11 | v ← u | przechodzimy do wierzchołka u |
K12: | Idź do kroku K03 | i wracamy na początek pętli |
Aby stworzyć implementację tego algorytmu, należy rozwiązać dwa problemy:
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 ):
|
Pascal// Wyszukiwanie cyklu lub ścieżki Eulera // Algorytm Fleury'ego // Data: 8.02.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program fleury; // Typy dla dynamicznej macierzy type nptr = array of byte; // Wiersz // Zmienne globalne var n, m, cv, sptr : integer; A : array of nptr; // Macierz sąsiedztwa S : array of integer; // Stos w tablicy D : array of integer; // Tablica numerów wierzchołków // Funkcja wyszukująca mosty w grafie // We: // v - numer wierzchołka startowego // vf - ojciec wierzchołka v na drzewie rozpinającym // Wy: // Parametr Low dla wierzchołka v //--------------------------------------------------- function DFSb ( v, vf : integer ) : integer; var Low, temp, i : integer; begin D [ v ] := cv; // Numerujemy wierzchołek Low := cv; // Wstępna wartość Low inc ( cv ); // Numer dla następnego wierzchołka for i := 0 to n - 1 do // Przeglądamy sąsiadów v if( A [ v ][ i ] > 0 ) and ( i <> vf ) then begin if D [ i ] = 0 then // Jeśli sąsiad nieodwiedzony, to begin temp :=DFSb ( i, v ); // to wywołujemy rekurencyjnie DFSb( ) if temp < Low then Low := temp; // Modyfikujemy Low end else if D [ i ] < Low then Low := D [ i ]; end; if( vf > -1 ) and ( Low = D [ v ] ) then // Mamy most? begin A [ vf ][ v ] := 2; // Oznaczamy krawędź vf-v jako most A [ v ][ vf ] := 2; end; DFSb := Low; end; // Procedura wyszukuje cykl lub ścieżkę Eulera // We: // v - wierzchołek startowy //-------------------------------------------- procedure findEuler ( v : integer ); var u, w, i : integer; begin while true do // W pętli przetwarzamy graf begin S [ sptr ] := v; // v umieszczamy na stosie inc ( sptr ); u := 0; // Szukamy pierwszego sąsiada v while( u < n ) and ( A [ v ][ u ] = 0 ) do inc ( u ); if u = n then break; // Nie ma sąsiadów, kończymy for i := 0 to n - 1 do D [ i ] := 0; // Zerujemy tablicę D cv := 1; // Numer pierwszego wierzchołka dla DFS DFSb ( v, -1 ); // Identyfikujemy krawędzie-mosty // Szukamy krawędzi nie będącej mostem w := u + 1; while( A [ v ][ u ] = 2 ) and ( w < n ) do begin if A [ v ][ w ] > 0 then u := w; inc ( w ); end; A [ v ][ u ] := 0; // Usuwamy krawędź v-u A [ u ][ v ] := 0; v := u; // Przechodzimy do u end; end; // ********************** // *** Program główny *** // ********************** var i, j, v1, v2 : integer; VD : array of integer; // Stopnie wierzchołków begin read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi SetLength ( A, n ); // Tworzymy tablicę wskaźników for i := 0 to n - 1 do SetLength ( A [ i ], n ); // Tworzymy wiersze macierzy sąsiedztwa // Macierz wypełniamy zerami for i := 0 to n - 1 do for j := 0 to n - 1 do A [ i ][ j ] := 0; SetLength ( VD, n ); // Tworzymy tablicę stopni for i := 0 to n - 1 do // Zerujemy tablicę stopni VD [ i ] := 0; SetLength ( D, n ); // Tworzymy tablicę numerów SetLength ( S, m+1 ); // Tworzymy pusty stos sptr := 0; // Odczytujemy kolejne definicje krawędzi for i := 1 to m do begin read ( v1, v2 ); // Wierzchołek startowy i końcowy krawędzi A [ v1 ][ v2 ] := 1; // Krawędź v1->v2 obecna A [ v2 ][ v1 ] := 1; // Krawędź v2->v1 obecna inc ( VD [ v1 ] ); inc ( VD [ v2 ] ); // Obliczamy stopnie v1 i v2 end; writeln; // Szukamy pozycji startowej v1 for v1 := 0 to n - 1 do if VD [ v1 ] > 0 then break; for i := v1 to n - 1 do if VD [ i ] mod 2 = 1 then begin v1 := i; break; end; // Wyznaczamy cykl lub ścieżkę Eulera findEuler ( v1 ); // Wypisujemy zawartość stosu if VD [ v1 ] mod 2 = 1 then write ( 'EULERIAN PATH :' ) else write ( 'EULERIAN CYCLE :' ); for i := 0 to sptr - 1 do write ( S [ i ] :3 ); writeln; // Usuwamy tablice dynamiczne for i := 0 to n - 1 do SetLength ( A [ i ], 0 ); SetLength ( A, 0 ); SetLength ( S, 0 ); SetLength ( D, 0 ); SetLength ( VD, 0 ); end. |
C++// Wyszukiwanie cyklu lub ścieżki Eulera // Algorytm Fleury'ego // Data: 8.02.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; // Zmienne globalne int n, m, cv, sptr; char **A; // Macierz sąsiedztwa int *S; // Stos w tablicy int *D; // Tablica numerów wierzchołków // Funkcja wyszukująca mosty w grafie // We: // v - numer wierzchołka startowego // vf - ojciec wierzchołka v na drzewie rozpinającym // Wy: // Parametr Low dla wierzchołka v //--------------------------------------------------- int DFSb ( int v, int vf ) { int Low, temp, i; D [ v ] = cv; // Numerujemy wierzchołek Low = cv; // Wstępna wartość Low cv++; // Numer dla następnego wierzchołka for( i = 0; i < n; i++ ) // Przeglądamy sąsiadów v if( A [ v ][ i ] && ( i != vf ) ) { if( !D [ i ] ) // Jeśli sąsiad nieodwiedzony, to { temp = DFSb ( i, v ); // to wywołujemy rekurencyjnie DFSb( ) if( temp < Low ) Low = temp; // Modyfikujemy Low } else if( D [ i ] < Low ) Low = D [ i ]; } if( ( vf > -1 ) && ( Low == D [ v ] ) ) // Mamy most? A [ vf ][ v ] = A [ v ][ vf ] = 2; // Oznaczamy krawędź vf-v jako most return Low; } // Procedura wyszukuje cykl lub ścieżkę Eulera // We: // v - wierzchołek startowy //-------------------------------------------- void findEuler ( int v ) { int u, w, i; while( true ) // W pętli przetwarzamy graf { S [ sptr++ ] = v; // v umieszczamy na stosie for( u = 0; ( u < n ) && !A [ v ][ u ];u++ ); // Szukamy pierwszego sąsiada v if( u == n ) break; // Nie ma sąsiadów, kończymy for( i = 0; i < n; i++ ) D [ i ] = 0; // Zerujemy tablicę D cv = 1; // Numer pierwszego wierzchołka dla DFS DFSb ( v, -1 ); // Identyfikujemy krawędzie-mosty // Szukamy krawędzi nie będącej mostem for( w = u + 1; ( A [ v ][ u ] == 2 ) && ( w < n ); w++ ) if( A [ v ][ w ] ) u = w; A [ v ][ u ] = A [ u ][ v ] = 0; // Usuwamy krawędź v-u v = u; // Przechodzimy do u } } // ********************** // *** Program główny *** // ********************** int main( ) { int i, j, v1, v2; int *VD; // Stopnie wierzchołków cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new char * [ n ]; // Tworzymy tablicę wskaźników for( i = 0; i < n; i++ ) A [ i ] = new char [ n ]; // Tworzymy wiersze macierzy sąsiedztwa // Macierz wypełniamy zerami for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) A [ i ][ j ] = 0; VD = new int [ n ]; // Tworzymy tablicę stopni for( i = 0; i < n; i++ ) // Zerujemy tablicę stopni VD [ i ] = 0; D = new int [ n ]; // Tworzymy tablicę numerów S = new int [ m + 1 ]; // Tworzymy pusty stos sptr = 0; // Odczytujemy kolejne definicje krawędzi for( i = 0; i < m; i++ ) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi A [ v1 ][ v2 ] = 1; // Krawędź v1->v2 obecna A [ v2 ][ v1 ] = 1; // Krawędź v2->v1 obecna VD [ v1 ] ++; VD [ v2 ] ++; // Obliczamy stopnie v1 i v2 } cout << endl; // Szukamy pozycji startowej v1 for( v1 = 0; v1 < n; v1++ ) if( VD [ v1 ] ) break; for( i = v1; i < n; i++ ) if( VD [ i ] % 2 ) { v1 = i; break; } // Wyznaczamy cykl lub ścieżkę Eulera findEuler ( v1 ); // Wypisujemy zawartość stosu if( VD [ v1 ] % 2 ) cout << "EULERIAN PATH :"; else cout << "EULERIAN CYCLE :"; for( i = 0; i < sptr; i++ ) cout << setw ( 3 ) << S [ i ]; cout << endl; // Usuwamy tablice dynamiczne for( i = 0; i < n; i++ ) delete [ ] A [ i ]; delete [ ] A; delete [ ] S; delete [ ] D; delete [ ] VD; return 0; } |
Basic' Wyszukiwanie cyklu lub ścieżki Eulera ' Algorytm Fleury'ego ' Data: 8.02.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Zmienne globalne Dim Shared As Integer n, m, cv, sptr Dim Shared As Byte Ptr Ptr A ' Macierz sąsiedztwa Dim Shared As Integer Ptr S ' Stos w tablicy Dim Shared As Integer Ptr D ' Tablica numerów wierzchołków ' Funkcja wyszukująca mosty w grafie ' We: ' v - numer wierzchołka startowego ' vf - ojciec wierzchołka v na drzewie rozpinającym ' Wy: ' Parametr Low dla wierzchołka v '--------------------------------------------------- function DFSb ( ByVal v As integer, ByVal vf As integer ) As Integer Dim As Integer Low, temp, i D [ v ] = cv ' Numerujemy wierzchołek Low = cv ' Wstępna wartość Low cv += 1 ' Numer dla następnego wierzchołka For i = 0 To n - 1 ' Przeglądamy sąsiadów v if( A [ v ][ i ] > 0 ) AndAlso ( i <> vf ) Then If D [ i ] = 0 Then ' Jeśli sąsiad nieodwiedzony, to temp = DFSb ( i, v ) ' to wywołujemy rekurencyjnie DFSb( ) If temp < Low Then Low = temp ' Modyfikujemy Low Else If D [ i ] < Low Then Low = D [ i ] End If End If Next if( vf > -1 ) AndAlso ( Low = D [ v ] ) Then ' Mamy most? A [ vf ][ v ] = 2: A [ v ][ vf ] = 2 ' Oznaczamy krawędź vf-v jako most End If Return Low End Function ' Procedura wyszukuje cykl lub ścieżkę Eulera ' We: ' v - wierzchołek startowy '-------------------------------------------- Sub findEuler ( ByVal v As integer ) Dim As Integer u, w, i While 1 ' W pętli przetwarzamy graf S [ sptr ] = v ' v umieszczamy na stosie sptr += 1 u = 0 while( u < n ) AndAlso ( A [ v ][ u ] = 0 ) ' Szukamy pierwszego sąsiada v u += 1 Wend If u = n Then Exit While ' Nie ma sąsiadów, kończymy For i = 0 To n - 1 D [ i ] = 0 ' Zerujemy tablicę D Next cv = 1 ' Numer pierwszego wierzchołka dla DFS DFSb ( v, -1 ) ' Identyfikujemy krawędzie-mosty ' Szukamy krawędzi nie będącej mostem w = u + 1 while( A [ v ][ u ] = 2 ) AndAlso ( w < n ) If A [ v ][ w ] > 0 Then u = w w += 1 Wend A [ v ][ u ] = 0: A [ u ][ v ] = 0 ' Usuwamy krawędź v-u v = u ' Przechodzimy do u Wend End Sub ' ********************** ' *** Program główny *** ' ********************** Dim As Integer i, j, v1, v2 Dim As Integer Ptr VD ' Stopnie wierzchołków Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New Byte Ptr [ n ] ' Tworzymy tablicę wskaźników For i = 0 To n - 1 A [ i ] = New Byte [ n ] ' Tworzymy wiersze macierzy sąsiedztwa Next ' Macierz wypełniamy zerami For i = 0 To n - 1 For j = 0 To n - 1 A [ i ][ j ] = 0 Next Next VD = New integer [ n ] ' Tworzymy tablicę stopni For i = 0 To n - 1 ' Zerujemy tablicę stopni VD [ i ] = 0 Next D = New integer [ n ] ' Tworzymy tablicę numerów S = New integer [ m + 1 ] ' Tworzymy pusty stos sptr = 0 ' Odczytujemy kolejne definicje krawędzi For i = 0 To m - 1 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi A [ v1 ][ v2 ] = 1 ' Krawędź v1->v2 obecna A [ v2 ][ v1 ] = 1 ' Krawędź v2->v1 obecna VD [ v1 ] += 1 VD [ v2 ] += 1 ' Obliczamy stopnie v1 i v2 Next Close #1 Print ' Szukamy pozycji startowej v1 v1 = 0 While v1 < n If VD [ v1 ] > 0 Then Exit While v1 += 1 Wend For i = v1 To n - 1 If VD [ i ] Mod 2 = 1 Then v1 = i Exit For End If Next ' Wyznaczamy cykl lub ścieżkę Eulera findEuler ( v1 ) ' Wypisujemy zawartość stosu If VD [ v1 ] Mod 2 = 1 Then Print "EULERIAN PATH :"; Else Print "EULERIAN CYCLE :"; End If For i = 0 To sptr - 1 Print Using "###";S [ i ]; Next Print ' Usuwamy tablice dynamiczne For i = 0 To n - 1 Delete [ ] A [ i ] Next Delete [ ] A Delete [ ] S Delete [ ] D Delete [ ] VD End |
Wynik: | |
xxx9 14 1 4 1 6 2 3 2 5 3 4 3 5 3 7 4 5 4 6 4 7 4 8 5 6 6 7 7 8 EULERIAN CYCLE : 1 4 3 2 5 3 7 4 5 6 4 8 7 6 1 |
![]() |
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 |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
v | – | wierzchołek startowy. |
w | – | wierzchołek bieżący. |
p | – | referencja do wskaźnika elementów dwukierunkowej listy wierzchołków C. |
visited | – | tablica logiczna wierzchołków odwiedzonych. |
u | – | wierzchołek, u ∈ C. |
K01: | visited [ w ] ← true | ustaw wierzchołek w jako odwiedzony |
K02: | Za p wstaw do listy C nowy element z wierzchołkiem w |
wierzchołek w stawiamy do cyklu |
K03: | p ← ( p→next ) | przesuń p na dodany element |
K04: | Dla każdego sąsiada u
wierzchołka w : wykonuj kroki K05...K11 |
przeglądamy sąsiadów wierzchołka w |
K05: | Jeśli u
≠ v, to idź do kroku K11 |
jeśli sąsiad nie jest wierzchołkiem startowym cyklu, idziemy dalej |
K06: | Za p
wstaw do listy C nowy element z wierzchołkiem v |
znaleźliśmy cykl, do listy C wstawiamy wierzchołek startowy |
K07: | Usuń krawędź ( p→v )–( p→next→v ) | z grafu usuwamy wszystkie krawędzie cyklu |
K08: |
Jeśli ( p→v ) = v, to zakończ z wynikiem true |
|
K09: | p ← ( p→prev ) | cofając się po liście wstecz w kierunku wierzchołka startowego |
K10: | Idź do kroku K07 | powrót na początek pętli |
K11: | Jeśli (
visited [ u ] = false )
![]() to zakończ z wynikiem true |
rekurencyjne wywołanie |
K12: | p ← ( p→prev ) | wierzchołek w nie należy do tego cyklu |
K13: | Usuń z listy C element wskazywany przez ( p→next ) |
usuwamy go z cyklu |
K14: | Zakończ z wynikiem false |
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. |
p | – | wskaźniki elementów listy C. |
visited | – | n elementowa tablica logiczna odwiedzin. |
K01: | Utwórz pustą listę C. | |
K02: | Utwórz n elementową tablicę visited | |
K03: | Wyszukaj w grafie wierzchołek v o niezerowym stopniu |
|
K04: | Umieść v na liście C | start cyklu |
K05: | Ustaw p na pierwszy element listy C | |
K06: | Dopóki p ≠ nil, wykonuj kroki K07...K10 |
idziemy wzdłuż elementów listy C |
K07: | Dopóki
wierzchołek ( p→v ) ma sąsiada u, wykonuj kroki K08...K09 |
|
K08: | Wyzeruj tablicę visited | |
K09: | DFSaddCycle ( n, graf, ( p→v ), u, p, visited ) | dodajemy do C nowy cykl |
K10: | p ← ( p→next ) | |
K11: | Zakończ |
Uwaga: wersja dla grafu nieskierowanego wymaga jedynie modyfikacji funkcji DFSfindCycle( ), tak aby szukała ścieżek w grafach nieskierowanych. Odpowiedni algorytm jest przedstawiony w rozdziale o znajdowaniu cykli w grafach.
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 ):
|
Pascal// Wyszukiwanie cyklu lub ścieżki Eulera // Algorytm Hierholzera // Data: 10.02.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- program hierholzer; // Typy danych type nptr = array of byte; // wiersz macierzy sąsiedztwa PdlistEl = ^dlistEl; // Wskaźnik elementów listy dwukierunkowej dlistEl = record next : PdlistEl; prev : PdlistEl; v : integer; end; // Zmienne globalne var m, n : integer; // Liczba krawędzi i wierzchołków graf: array of nptr; // Dynamiczna macierz sąsiedztwa visited : array of boolean; // Tablica odwiedzin // Procedury obsługi listy dwukierunkowej //--------------------------------------- // Procedura dołącza do listy nowy element // za elementem wskazywanym przez p //------------------------------------------ procedure addC ( x : integer; p : PdlistEl ); var r : PdlistEl; begin new ( r ); r^.v := x; r^.next := p^.next; if r^.next <> nil then r^.next^.prev := r; r^.prev := p; p^.next := r; end; // Procedura usuwa z listy element wskazywany przez p //--------------------------------------------------- procedure remC ( p : PdlistEl ); begin if p^.next <> nil then p^.next^.prev := p^.prev; if p^.prev <> nil then p^.prev^.next := p^.next; dispose ( p ); end; // Rekurencyjna funkcja dodająca do listy nowy cykl // v - wierzchołek startowy i końcowy cyklu // w - wierzchołek bieżący // p - referencja do wskazania punktu wstawiania na liście //-------------------------------------------------------- function DFSaddCycle ( v, w : integer; var p : PdlistEl ) : boolean; var u : integer; begin visited [ w ] := true; // Oznaczamy v jako odwiedzony addC ( w, p ); // Dodajemy w do cyklu p := p^.next; // p wskazuje dodany element for u := 0 to n - 1 do // Przeglądamy sąsiadów w if graf [ w ][ u ] = 1 then begin if u = v then // Cykl znaleziony? begin addC ( v, p ); // Zamykamy cykl na liście C repeat graf [ p^.v ][ p^.next^.v ] := 0; // Usuwamy krawędzie cyklu if p^.v = v then Exit ( true ); p := p^.prev; until false; end; if not visited [ u ] and DFSaddCycle ( v, u, p ) then Exit ( true ); end; p := p^.prev; // Z listy usuwamy w remC ( p^.next ); DFSaddCycle := false; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** var i, j, v1, v2 : integer; C : PdlistEl; // Lista cyklu Eulera p : PdlistEl; begin read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi // Tworzymy tablice dynamiczne SetLength ( graf, n ); SetLength ( visited, n ); for i := 0 to n - 1 do begin SetLength ( graf [ i ], n ); for j := 0 to n - 1 do graf [ i ][ j ] := 0; end; // Odczytujemy definicje krawędzi grafu for i := 0 to m - 1 do begin read ( v1, v2 ); graf [ v1 ][ v2 ] := 1; end; new ( c ); // Tworzymy listę z wierzchołkiem v1 C^.v := v1; C^.next := nil; C^.prev := nil; p := C; // p wskazuje pierwszy element listy while p <> nil do // Przeglądamy listę C begin for i := 0 to n - 1 do // Szukamy sąsiadów if graf [ p^.v ][ i ] = 1 then begin for j := 0 to n - 1 do visited [ j ] := false; DFSaddCycle ( p^.v, i, p ); // Dla każdego sąsiada uruchamiamy szukanie cyklu end; p := p^.next; // Następny element listy C end; writeln; // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera p := C; while p <> nil do begin write ( p^.v:3 ); p := p^.next; end; writeln; // Usuwamy zmienne dynamiczne p := C; while p <> nil do begin p := C^.next; remC ( c ); C := p; end; for i := 0 to n - 1 do SetLength ( graf [ i ], 0 ); SetLength ( graf, 0 ); SetLength ( visited, 0 ); end. |
C++// Wyszukiwanie cyklu lub ścieżki Eulera // Algorytm Hierholzera // Data: 10.02.2014 // (C)2014 mgr Jerzy Wałaszek //--------------------------- #include <iostream> #include <iomanip> using namespace std; // Typy danych struct dlistEl { dlistEl *next, *prev; int v; }; // Zmienne globalne int m, n; // Liczba krawędzi i wierzchołków char **graf; // Dynamiczna macierz sąsiedztwa bool * visited; // Tablica odwiedzin // Procedury obsługi listy dwukierunkowej //--------------------------------------- // Procedura dołącza do listy nowy element // za elementem wskazywanym przez p //------------------------------------------ void addC ( int x, dlistEl *p ) { dlistEl * r; r = new dlistEl; r->v = x; r->next = p->next; if( r->next ) r->next->prev = r; r->prev = p; p->next = r; } // Procedura usuwa z listy element wskazywany przez p //--------------------------------------------------- void remC ( dlistEl *p ) { if( p->next ) p->next->prev = p->prev; if( p->prev ) p->prev->next = p->next; delete p; } // Rekurencyjna funkcja dodająca do listy nowy cykl // v - wierzchołek startowy i końcowy cyklu // w - wierzchołek bieżący // p - referencja do wskazania punktu wstawiania na liście //-------------------------------------------------------- bool DFSaddCycle ( int v, int w, dlistEl * & p ) { int u; visited [ w ] = true; // Oznaczamy v jako odwiedzony addC ( w, p ); // Dodajemy w do cyklu p = p->next; // p wskazuje dodany element for( u = 0; u < n; u++ ) // Przeglądamy sąsiadów w if( graf [ w ][ u ] ) { if( u == v ) // Cykl znaleziony? { addC ( v, p ); // Zamykamy cykl na liście C do { graf [ p->v ][ p->next->v ] = 0; // Usuwamy krawędzie cyklu if( p->v == v ) return true; p = p->prev; } while( true ); } if( !visited [ u ] && DFSaddCycle ( v, u, p ) ) return true; } p = p->prev; // Z listy usuwamy w remC ( p->next ); return false; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main( ) { int i, j, v1, v2; dlistEl *C, *p; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi // Tworzymy tablice dynamiczne graf = new char * [ n ]; visited = new bool [ n ]; for( i = 0; i < n; i++ ) { graf [ i ] = new char [ n ]; for( j = 0; j < n; j++ ) graf [ i ][ j ] = 0; } // Odczytujemy definicje krawędzi grafu for( i = 0; i < m; i++ ) { cin >> v1 >> v2; graf [ v1 ][ v2 ] = 1; } C = new dlistEl; // Tworzymy listę z wierzchołkiem v1 C->v = v1; C->next = NULL; C->prev = NULL; for( p = C; p; p = p->next ) // Przeglądamy listę C for( i = 0; i < n; i++ ) // Szukamy sąsiadów if( graf [ p->v ][ i ] ) { for( j = 0; j < n; j++ ) visited [ j ] = false; DFSaddCycle ( p->v, i, p ); // Dla każdego sąsiada uruchamiamy szukanie cyklu } cout << endl; // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera for( p = C; p; p = p->next ) cout << setw ( 3 ) << p->v; cout << endl; // Usuwamy zmienne dynamiczne p = C; while( p ) { p = C->next; remC ( c ); C = p; } for( i = 0; i < n; i++ ) delete [ ] graf [ i ]; delete [ ] graf; delete [ ] visited; return 0; } |
Basic' Wyszukiwanie cyklu lub ścieżki Eulera ' Algorytm Hierholzera ' Data: 10.02.2014 ' (C)2014 mgr Jerzy Wałaszek '--------------------------- ' Typy danych Type dlistEl Next As dlistEl Ptr prev As dlistEl Ptr v As Integer End Type ' Zmienne globalne Dim Shared As Integer m, n ' Liczba krawędzi i wierzchołków Dim Shared As Byte Ptr Ptr graf ' Dynamiczna macierz sąsiedztwa Dim Shared As Byte Ptr visited ' Tablica odwiedzin ' Procedury obsługi listy dwukierunkowej '--------------------------------------- ' Procedura dołącza do listy nowy element ' za elementem wskazywanym przez p '------------------------------------------ Sub addC ( ByVal x As Integer, ByVal p As dlistEl Ptr ) Dim As dlistEl Ptr r r = new dlistEl r->v = x r->next = p->Next If r->Next Then r->next->prev = r r->prev = p p->next = r End Sub ' Procedura usuwa z listy element wskazywany przez p '--------------------------------------------------- Sub remC ( ByVal p As dlistEl Ptr ) If p->Next Then p->next->prev = p->prev If p->prev Then p->prev->next = p->Next Delete p End Sub ' Rekurencyjna funkcja dodająca do listy nowy cykl ' v - wierzchołek startowy i końcowy cyklu ' w - wierzchołek bieżący ' p - referencja do wskazania punktu wstawiania na liście '-------------------------------------------------------- Function DFSaddCycle ( ByVal v As integer, ByVal w As integer, ByRef p As dlistEl Ptr ) As Integer Dim As Integer u visited [ w ] = 1 ' Oznaczamy v jako odwiedzony addC ( w, p ) ' Dodajemy w do cyklu p = p->Next ' p wskazuje dodany element For u = 0 To n - 1 ' Przeglądamy sąsiadów w If graf [ w ][ u ] > 0 Then If u = v Then ' Cykl znaleziony? addC ( v, p ) ' Zamykamy cykl na liście C Do graf [ p->v ][ p->next->v ] = 0 ' Usuwamy krawędzie cyklu If p->v = v then return 1 p = p->prev loop While 1 End If if( visited [ u ] = 0 ) AndAlso ( DFSaddCycle ( v, u, p ) = 1 ) Then return 1 End If Next p = p->prev ' Z listy usuwamy w remC ( p->next ) return 0 End Function ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As integer i, j, v1, v2 Dim As dlistEl Ptr p, C Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi ' Tworzymy tablice dynamiczne graf = New Byte Ptr [ n ] visited = New Byte [ n ] For i = 0 To n - 1 graf [ i ] = New Byte [ n ] For j = 0 To n - 1: graf [ i ][ j ] = 0: Next Next ' Odczytujemy definicje krawędzi grafu For i = 0 To m - 1 Input #1, v1, v2 graf [ v1 ][ v2 ] = 1 Next Close #1 C = New dlistEl ' Tworzymy listę z wierzchołkiem v1 C->v = v1 C->next = 0 C->prev = 0 p = C While p ' Przeglądamy listę C For i = 0 To n - 1 ' Szukamy sąsiadów If graf [ p->v ][ i ] = 1 Then For j = 0 To n - 1: visited [ j ] = 0: Next DFSaddCycle ( p->v, i, p ) ' Dla każdego sąsiada uruchamiamy szukanie cyklu End If Next p = p->Next Wend Print ' Wyświetlamy zawartość listy C, czyli pełny cykl Eulera p = C while p <> 0 Print Using "###";p->v; p = p->Next Wend Print ' Usuwamy zmienne dynamiczne p = C While p p = C->Next remC ( c ) C = p Wend For i = 0 To n - 1: Delete [ ] graf [ i ] : Next Delete [ ] graf Delete [ ] visited End |
Wynik: | |
9 17 0 1 1 3 1 4 2 1 2 5 3 0 3 2 3 7 4 2 4 3 4 6 5 4 5 7 6 3 7 4 7 8 8 5 8 5 7 4 6 3 0 1 4 3 2 5 4 2 1 3 7 8 |
![]() |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 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.