![]() |
Wyjście Spis treści Poprzedni Następny
Autor artykułu: mgr Jerzy Wałaszek, wersja 2.0 |
©2014 mgr Jerzy Wałaszek |
Zbadać, czy dany graf jest cykliczny
Cykl jest ścieżką, która rozpoczyna się i kończy w tym samym wierzchołku. Aby stwierdzić, czy graf zawiera jakiś cykl, przechodzimy go algorytmem DFS. Jeśli w trakcie przechodzenia natrafimy na wierzchołek już odwiedzony, a nie jest to wierzchołek, z którego przyszliśmy, to graf jest cykliczny. W przeciwnym razie graf jest acykliczny.
Prześledźmy na prostym przykładzie badanie cykliczności grafu.
![]() |
Rozpoczynamy przejście DFS od wierzchołka 0. |
![]() |
Przechodzimy do wierzchołka 1. Wierzchołek 0 będzie ignorowany, ponieważ przyszliśmy z niego (na danym etapie algorytm zawsze musi "wiedzie", skąd nastąpiło przyjście do bieżącego wierzchołka). |
![]() |
Przechodzimy do wierzchołka 2. Wierzchołek 1 będzie ignorowany, ponieważ przyszliśmy z niego. |
![]() |
Przechodzimy do wierzchołka 3. Wierzchołek 2 będzie ignorowany. |
![]() |
Ponieważ wierzchołek 3 nie posiada dalszych sąsiadów, wracamy do wierzchołka 2 (uwaga, to nie jest przejście do wierzchołka 2, lecz powrót z gałęzi grafu, która została już w całości przebyta). |
![]() |
Wierzchołek 2 nie posiada dalszych sąsiadów, wracamy do wierzchołka 1. Kontynuujemy przeglądanie dalszych sąsiadów wierzchołka 1. |
![]() |
Przechodzimy do wierzchołka 4. Wierzchołek 1 ignorujemy, ponieważ przyszliśmy z niego. |
![]() |
Przechodzimy do wierzchołka 5. |
![]() |
W wierzchołku 5 natrafiamy na sąsiada 1, który był już wcześniej odwiedzony, a nie przyszliśmy do wierzchołka 5 z wierzchołka 1 (tylko z wierzchołka 4). Wykryliśmy cykl. Algorytm kończymy z wynikiem pozytywnym – graf jest cykliczny. |
Jeśli graf nieskierowany nie posiada cykli, to jest drzewem.
n | – | liczba wierzchołków w grafie, n
![]() |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje |
false – graf nie jest cykliczny
S | – | stos liczb całkowitych |
w,v,z | – | wierzchołki robocze, w,v,z
![]() |
visited | – | n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych |
K01: | Utwórz n elementową tablicę visited | |
K02: | Ustaw wszystkie elementy tablicy visited na false | |
K03: | Utwórz pusty stos S | |
K04: | S.push(0) | ; na stosie umieszczamy numer wierzchołka startowego |
K05: | S.push(-1) | ; oraz numer wierzchołka, z którego przyszliśmy, -1 = żaden |
K06: | visited[0] ← true | ; wierzchołek zaznaczamy jako odwiedzony |
K07: | Dopóki S.empty() = false, wykonuj K08...K12 | ; w pętli przechodzimy graf algorytmem DFS |
K08: | w ← S.top(); S.pop() | ; w – wierzchołek, z którego przyszliśmy |
K09: | v ← S.top(); S.pop() | ; v – wierzchołek bieżący |
K10: | Dla każdego sąsiada z wierzchołka v wykonuj K11...K12 | |
K11: |
Jeśli visited[z] = false, to S.push(z) S.push(v) visited[z] ← true Następny obieg pętli K10 |
; jeśli sąsiad nie jest odwiedzony, ; to umieszczamy go na stosie ; wraz z numerem bieżącego wierzchołka |
K12: | Jeśli z ≠ w, to zakończ z wynikiem true | ; trafiliśmy na odwiedzony wierzchołek, z
którego nie przyszliśmy ; graf jest cykliczny |
K13: | Zakończ z wynikiem false | ; nigdzie nie natrafiliśmy na odwiedzony
wcześniej wierzchołek ; graf nie jest cykliczny |
Ważne: 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. |
Przykładowe dane dla programu:
Graf cykliczny![]() |
6 6 0 1 1 2 1 4 1 5 2 3 4 5 |
Graf niecykliczny
(drzewo)![]() |
6 5 0 1 1 2 1 4 2 3 4 5 |
Lazarus | |
// Badanie cykliczności spójnego grafu nieskierowanego // Data: 10.12.2013 // (C)2013 mgr Jerzy Wałaszek //---------------------------------------------------- program testcyclic; // Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu type PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; // Definicja typu obiektowego stack //--------------------------------- stack = object private S : PslistEl; // lista przechowująca stos public constructor init; destructor destroy; function empty : boolean; function top : integer; procedure push(v : integer); procedure pop; end; // Konstruktor //------------ constructor stack.init; begin S := nil; end; // Destruktor //----------- destructor stack.destroy; begin while S <> nil do pop; end; // Sprawdza, czy stos jest pusty //------------------------------ function stack.empty : boolean; begin if S = nil then empty := true else empty := false; end; // Zwraca liczbę ze szczytu stosu //---------------------------------- function stack.top : integer; begin top := S^.v; end; // Umieszcza dane na stosie //------------------------- procedure stack.push(v : integer); var e : PslistEl; begin new(e); e^.v := v; e^.next := S; S := e; end; // Usuwa dane ze stosu //-------------------- procedure stack.pop; var e :PslistEl; begin if S <> NIL then begin e := S; S := S^.next; dispose(e); end; end; // Funkcja bada cykliczność grafu //------------------------------- function isCyclic(n : integer; var G : TList) : boolean; var S : stack; // Stos visited : array of boolean; // Tablica odwiedzin p : PslistEl; // Wskaźnik elementu listy w,v,z,i : integer; // Zmienne pomocnicze begin SetLength(visited,n); // Tworzymy tablicę odwiedzin for i := 0 to n - 1 do visited[i] := false; // i zerujemy ją S.init; // Tworzymy pusty stos S.push(0); S.push(-1); // Na stos wierzchołek startowy i -1 visited[0] := true; // Oznaczamy wierzchołek jako odwiedzony while S.empty = false do // W pętli przechodzimy graf za pomocą DFS begin w := S.top; S.pop; // Pobieramy ze stosu wierzchołek z którego przyszliśmy v := S.top; S.pop; // oraz wierzchołek bieżący p := G[v]; // Przeglądamy jego listę sąsiadów while p <> nil do begin z := p^.v; // Numer sąsiada if not visited[z] then begin S.push(z); S.push(v); // Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] := true; // Oznaczamy go jako odwiedzonego end else if z <> w then // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem begin // z którego przyszliśmy, to odkryliśmy cykl SetLength(visited,0); // Usuwamy zmienne pomocnicze S.destroy; Exit(true); // Kończymy z wynikiem true end; p := p^.next; end; end; SetLength(visited,0); // W grafie nie ma cykli. S.destroy; Exit(false); // Kończymy z wynikiem false end; // ********************** // *** Program główny *** // ********************** var n,m,i,v1,v2 : integer; p,r : PslistEl; A : TList; begin read(n,m); // Czytamy liczbę wierzchołków i krawędzi SetLength(A,n); // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for i := 0 to n - 1 do A[i] := nil; // Odczytujemy kolejne definicje krawędzi for i := 0 to m - 1 do begin read(v1,v2); // Wierzchołek startowy i końcowy krawędzi new(p); // Tworzymy nowy element p^.v := v2; // Numerujemy go jako v2 p^.next := A[v1]; // Dodajemy go na początek listy A[v1] A[v1] := p; new(p); // Krawędź w drugą stronę, bo graf jest nieskierowany p^.v := v1; p^.next := A[v2]; A[v2] := p; end; if isCyclic(n,A) then writeln('CYCLIC GRAPH') else writeln('ACYCLIC GRAPH'); // Usuwamy tablicę list sąsiedztwa for i := 0 to n - 1 do begin p := A[i]; while p <> nil do begin r := p; p := p^.next; dispose(r); end; end; SetLength(A,0); end. |
|
Code::Blocks | |
// Badanie cykliczności spójnego grafu nieskierowanego // Data: 10.12.2013 // (C)2013 mgr Jerzy Wałaszek //---------------------------------------------------- #include <iostream> using namespace std; // Typy dla dynamicznej tablicy list sąsiedztwa i stosu struct slistEl { slistEl * next; int v; }; class stack { private: slistEl * S; // lista przechowująca stos public: stack(); // konstruktor ~stack(); // destruktor bool empty(void); int top(void); void push(int v); void pop(void); }; //--------------------- // Metody obiektu stack //--------------------- // Konstruktor //------------ stack::stack() { S = NULL; } // Destruktor - zwalnia tablicę dynamiczną //---------------------------------------- stack::~stack() { while(S) pop(); } // Sprawdza, czy stos jest pusty //------------------------------ bool stack::empty(void) { return !S; } // Zwraca szczyt stosu //-------------------- int stack::top(void) { return S->v; } // Zapisuje na stos //----------------- void stack::push(int v) { slistEl * e = new slistEl; e->v = v; e->next = S; S = e; } // Usuwa ze stosu //--------------- void stack::pop(void) { if(S) { slistEl * e = S; S = S->next; delete e; } } // Funkcja bada cykliczność grafu //------------------------------- bool isCyclic(int n, slistEl ** G) { stack S; // Stos bool * visited; // Tablica odwiedzin slistEl * p; // Wskaźnik elementu listy int w,v,z,i; // Zmienne pomocnicze visited = new bool[n]; // Tworzymy tablicę odwiedzin for(i = 0; i < n; i++) visited[i] = false; // i zerujemy ją S.push(0); S.push(-1); // Na stos wierzchołek startowy i -1 visited[0] = true; // Oznaczamy wierzchołek jako odwiedzony while(!S.empty()) // W pętli przechodzimy graf za pomocą DFS { w = S.top(); S.pop(); // Pobieramy ze stosu wierzchołek z którego przyszliśmy v = S.top(); S.pop(); // oraz wierzchołek bieżący for(p = G[v]; p; p = p->next) // Przeglądamy jego listę sąsiadów { z = p->v; // Numer sąsiada if(!visited[z]) { S.push(z); S.push(v); // Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] = true; // Oznaczamy go jako odwiedzonego } else if(z != w) // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem { // z którego przyszliśmy, to odkryliśmy cykl delete [] visited; // Usuwamy zmienne pomocnicze return true; // Kończymy z wynikiem true } } } delete [] visited; // W grafie nie ma cykli. return false; // Kończymy z wynikiem false } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { int n,m,i,v1,v2; slistEl * p,* r,** A; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for(i = 0; i < n; i++) A[i] = NULL; // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi p = new slistEl; // Tworzymy nowy element p->v = v2; // Numerujemy go jako v2 p->next = A[v1]; // Dodajemy go na początek listy A[v1] A[v1] = p; p = new slistEl; // Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1; p->next = A[v2]; A[v2] = p; } if(isCyclic(n,A)) cout << "CYCLIC GRAPH"; else cout << "ACYCLIC GRAPH"; cout << endl; // Usuwamy tablicę list sąsiedztwa for(i = 0; i < n; i++) { p = A[i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; return 0; } |
|
Free Basic | |
' Badanie cykliczności spójnego grafu nieskierowanego ' Data: 10.12.2013 ' (C)2013 mgr Jerzy Wałaszek '---------------------------------------------------- ' Typy dla dynamicznej tablicy list sąsiedztwa i stosu Type slistEl next As slistEl Ptr v As Integer End Type Type stack Private: S As slistEl Ptr ' lista zawierająca stos Public: Declare Constructor() Declare Destructor() Declare Function empty() As Integer Declare Function top As Integer Declare Sub push(ByVal v As Integer) Declare Sub pop() End Type '--------------------- ' Metody obiektu stack '--------------------- ' Konstruktor '------------ Constructor stack() S = 0 End Constructor ' Destruktor '----------- Destructor stack() While S pop() Wend End Destructor ' Sprawdza, czy stos jest pusty '------------------------------ Function stack.empty() As Integer If S = 0 Then Return 1 Return 0 End Function ' Zwraca szczyt stosu. '------------------------------ Function stack.top() As Integer top = S->v End Function ' Zapisuje na stos '----------------- Sub stack.push(ByVal v As Integer) Dim e As slistEl Ptr e = New slistEl e->v = v e->Next = S S = e End Sub ' Usuwa ze stosu '--------------- Sub stack.pop() Dim e As slistEl Ptr If S Then e = S S = S->Next Delete e End If End Sub ' Funkcja bada cykliczność grafu '------------------------------- Function isCyclic(ByVal n As Integer, ByVal G As slistEl Ptr Ptr) As Integer Dim As stack S ' Stos Dim As Integer ptr visited ' Tablica odwiedzin Dim As slistEl Ptr p ' Wskaźnik elementu listy Dim As Integer w,v,z,i ' Zmienne pomocnicze visited = new Integer [n] ' Tworzymy tablicę odwiedzin For i = 0 To n - 1 visited[i] = 0 ' i zerujemy ją Next S.push(0): S.push(-1) ' Na stos wierzchołek startowy i -1 visited[0] = 1 ' Oznaczamy wierzchołek jako odwiedzony While S.empty() = 0 ' W pętli przechodzimy graf za pomocą DFS w = S.top(): S.pop() ' Pobieramy ze stosu wierzchołek z którego przyszliśmy v = S.top(): S.pop() ' oraz wierzchołek bieżący p = G[v] While p ' Przeglądamy jego listę sąsiadów z = p->v ' Numer sąsiada If visited[z] = 0 Then S.push(z): S.push(v) ' Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] = 1 ' Oznaczamy go jako odwiedzonego ElseIf z <> w Then ' Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem Delete [] visited ' z którego przyszliśmy, to odkryliśmy cykl Return 1 ' Usuwamy zmienne pomocnicze i kończymy z wynikiem true EndIf p = p->Next Wend Wend Delete [] visited ' W grafie nie ma cykli. return 0 ' Kończymy z wynikiem false End Function ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer n,m,i,v1,v2 Dim As slistEl Ptr p,r Dim As slistEl Ptr Ptr A Open Cons For Input As #1 Input #1,n,m ' Czytamy liczbę wierzchołków i krawędzi A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa ' Tablicę wypełniamy pustymi listami For i = 0 To n - 1 A[i] = 0 Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m -1 Input #1,v1,v2 ' Wierzchołek startowy i końcowy krawędzi p = new slistEl ' Tworzymy nowy element p->v = v2 ' Numerujemy go jako v2 p->next = A[v1] ' Dodajemy go na początek listy A[v1] A[v1] = p p = new slistEl ' Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1 p->next = A[v2] A[v2] = p Next Close #1 If isCyclic(n,A) Then Print "CYCLIC GRAPH" Else Print "ACYCLIC GRAPH" EndIf ' Usuwamy tablicę list sąsiedztwa For i = 0 To n - 1 p = A[i] While p r = p p = p->Next Delete r Wend Next Delete [] A End |
|
Wynik | |
6 6 0 1 1 2 1 4 1 5 2 3 4 5 CYCLIC GRAPH |
6 5 0 1 1 2 1 4 2 3 4 5 ACYCLIC GRAPH |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje |
v | – | numer wierzchołka startowego, v
![]() |
visited | – | n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych |
false – graf nie jest cykliczny
S | – | stos liczb całkowitych |
w,z | – | wierzchołki robocze, w,v,z
![]() |
K01: | Utwórz pusty stos S | |
K02: | S.push(v); S.push(-1) | ; na stosie umieszczamy numer wierzchołka startowego i -1 |
K03: | visited[v] ← true | ; wierzchołek oznaczamy jako odwiedzony |
K04: | Dopóki S.empty() = false, wykonuj K05...K09 | ; w pętli przechodzimy graf algorytmem DFS |
K05: | w ← S.top(); S.pop() | ; w – wierzchołek, z którego przyszliśmy |
K06: | v ← S.top(); S.pop() | ; v – wierzchołek bieżący |
K07: | Dla każdego sąsiada z wierzchołka v wykonuj K08...K09 | |
K08: |
Jeśli visited[z] = false, to S.push(z) S.push(v) visited[z] ← true Następny obieg pętli K07 |
; jeśli sąsiad nie jest odwiedzony, ; to umieszczamy go na stosie ; wraz z numerem bieżącego wierzchołka |
K09: | Jeśli z ≠ w, to zakończ z wynikiem true | ; trafiliśmy na odwiedzony wierzchołek, z
którego nie przyszliśmy ; graf jest cykliczny |
K10: | Zakończ z wynikiem false | ; nigdzie nie natrafiliśmy na odwiedzony
wcześniej wierzchołek ; graf nie jest cykliczny |
n | – | liczba wierzchołków w grafie, n
![]() |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje |
false – graf nie jest cykliczny
i | – | wierzchołek startowy, i
![]() |
visited | – | n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych |
K01: | Utwórz n elementową tablicę visited | |
K02: | Ustaw wszystkie elementy tablicy visited na false | |
K03: | Dla i = 0,1,...,n-1, wykonuj K04..K05 | ; szukamy pierwszego nieodwiedzonego jeszcze wierzchołka |
K04: | Jeśli visited[i] = true, to następny obieg pętli K3 | |
K05: | Jeśli isComponentCyclic(graf,i,visited) = true, to zakończ z wynikiem true | ; sprawdzamy cykliczność składowej zawierającej znaleziony wierzchołek |
K06: | Zakończ z wynikiem false |
Ważne: 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. |
Przykładowe dane dla programu:
Niespójny graf cykliczny![]() |
12 11 0 1 1 8 2 3 2 5 3 7 4 9 5 8 5 10 6 9 6 11 7 10 |
Niespójny graf niecykliczny![]() |
12 10 0 1 1 8 2 3 2 5 4 9 5 8 5 10 6 9 6 11 7 10 |
Lazarus | |
// Badanie cykliczności niespójnego grafu nieskierowanego // Data: 14.12.2013 // (C)2013 mgr Jerzy Wałaszek //-------------------------------------------------------- program project1; // Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu type PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; // Definicja typu obiektowego stack //--------------------------------- stack = object private S : PslistEl; // lista przechowująca stos public constructor init; destructor destroy; function empty : boolean; function top : integer; procedure push(v : integer); procedure pop; end; // Konstruktor //------------ constructor stack.init; begin S := nil; end; // Destruktor //----------- destructor stack.destroy; begin while S <> nil do pop; end; // Sprawdza, czy stos jest pusty //------------------------------ function stack.empty : boolean; begin if S = nil then empty := true else empty := false; end; // Zwraca liczbę ze szczytu stosu //---------------------------------- function stack.top : integer; begin top := S^.v; end; // Umieszcza dane na stosie //------------------------- procedure stack.push(v : integer); var e : PslistEl; begin new(e); e^.v := v; e^.next := S; S := e; end; // Usuwa dane ze stosu //-------------------- procedure stack.pop; var e :PslistEl; begin if S <> NIL then begin e := S; S := S^.next; dispose(e); end; end; // Funkcja bada cykliczność składowej grafu //----------------------------------------- function isComponentCyclic(var G : TList; v : integer; var visited : array of boolean) : boolean; var S : stack; // Stos p : PslistEl; // Wskaźnik elementu listy w,z : integer; // Zmienne pomocnicze begin S.init; // Tworzymy pusty stos S.push(v); S.push(-1); // Na stos wierzchołek startowy i -1 visited[v] := true; // Oznaczamy wierzchołek startowy jako odwiedzony while S.empty = false do // W pętli przechodzimy graf za pomocą DFS begin w := S.top; S.pop; // Pobieramy ze stosu wierzchołek z którego przyszliśmy v := S.top; S.pop; // oraz wierzchołek bieżący p := G[v]; // Przeglądamy jego listę sąsiadów while p <> nil do begin z := p^.v; // Numer sąsiada if visited[z] = false then begin S.push(z); S.push(v); // Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] := true; end else if z <> w then // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem begin // z którego przyszliśmy, to odkryliśmy cykl S.destroy; Exit(true); // Kończymy z wynikiem true end; p := p^.next; end; end; S.destroy; Exit(false); // Kończymy z wynikiem false end; // Funkcja bada cykliczność grafu //------------------------------- function isCyclic(n : integer; var G : Tlist) : boolean; var i : integer; visited : array of boolean; begin SetLength(visited,n); // Tworzymy tablicę odwiedzin for i := 0 to n - 1 do visited[i] := false; // Tablicę zerujemy for i := 0 to n - 1 do // Szukamy wierzchołka startowego if (visited[i] = false) and (isComponentCyclic(G,i,visited) = true) then begin SetLength(visited,0); Exit(true); // Cykl znaleziony, kończymy z true end; SetLength(visited,0); Exit(false); // Graf nie posiada cyklu, kończymy z false end; // ********************** // *** Program główny *** // ********************** var n,m,i,v1,v2 : integer; p,r : PslistEl; A : TList; begin read(n,m); // Czytamy liczbę wierzchołków i krawędzi SetLength(A,n); // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for i := 0 to n - 1 do A[i] := nil; // Odczytujemy kolejne definicje krawędzi for i := 0 to m - 1 do begin read(v1,v2); // Wierzchołek startowy i końcowy krawędzi new(p); // Tworzymy nowy element p^.v := v2; // Numerujemy go jako v2 p^.next := A[v1]; // Dodajemy go na początek listy A[v1] A[v1] := p; new(p); // Krawędź w drugą stronę, bo graf jest nieskierowany p^.v := v1; p^.next := A[v2]; A[v2] := p; end; if isCyclic(n,A) then writeln('CYCLIC GRAPH') else writeln('ACYCLIC GRAPH'); // Usuwamy tablicę list sąsiedztwa for i := 0 to n - 1 do begin p := A[i]; while p <> nil do begin r := p; p := p^.next; dispose(r); end; end; SetLength(A,0); end. |
|
Code::Blocks | |
// Badanie cykliczności niespójnego grafu nieskierowanego // Data: 14.12.2013 // (C)2013 mgr Jerzy Wałaszek //-------------------------------------------------------- #include <iostream> using namespace std; // Typy dla dynamicznej tablicy list sąsiedztwa i stosu struct slistEl { slistEl * next; int v; }; class stack { private: slistEl * S; // lista przechowująca stos public: stack(); // konstruktor ~stack(); // destruktor bool empty(void); int top(void); void push(int v); void pop(void); }; //--------------------- // Metody obiektu stack //--------------------- // Konstruktor //------------ stack::stack() { S = NULL; } // Destruktor - zwalnia tablicę dynamiczną //---------------------------------------- stack::~stack() { while(S) pop(); } // Sprawdza, czy stos jest pusty //------------------------------ bool stack::empty(void) { return !S; } // Zwraca szczyt stosu //-------------------- int stack::top(void) { return S->v; } // Zapisuje na stos //----------------- void stack::push(int v) { slistEl * e = new slistEl; e->v = v; e->next = S; S = e; } // Usuwa ze stosu //--------------- void stack::pop(void) { if(S) { slistEl * e = S; S = S->next; delete e; } } // Funkcja bada cykliczność składowej grafu //----------------------------------------- bool isComponentCyclic(slistEl ** G, int v, bool * visited) { stack S; // Stos slistEl * p; // Wskaźnik elementu listy int w,z; // Zmienne pomocnicze S.push(v); S.push(-1); // Na stos wierzchołek startowy i -1 visited[v] = true; // Wierzchołek startowy oznaczamy jako odwiedzony while(!S.empty()) // W pętli przechodzimy graf za pomocą DFS { w = S.top(); S.pop(); // Pobieramy ze stosu wierzchołek z którego przyszliśmy v = S.top(); S.pop(); // oraz wierzchołek bieżący for(p = G[v]; p; p = p->next) // Przeglądamy listę sąsiadów { z = p->v; // Numer sąsiada if(!visited[z]) { S.push(z); S.push(v); // Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] = true; } else if(z != w) // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem // z którego przyszliśmy, to odkryliśmy cykl return true; // Kończymy z wynikiem true } } return false; // Kończymy z wynikiem false } // Funkcja bada cykliczność grafu //------------------------------- bool isCyclic(int n, slistEl ** G) { int i; bool * visited; visited = new bool [n]; // Tworzymy tablicę odwiedzin for(i = 0; i < n; i++) visited[i] = false; // Tablicę zerujemy for(i = 0; i < n; i++) // Szukamy wierzchołka startowego if(!visited[i] && isComponentCyclic(G,i,visited)) { delete [] visited; return true; // Cykl znaleziony, kończymy z true } delete [] visited; return false; // Graf nie posiada cyklu, kończymy z false } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { int n,m,i,v1,v2; slistEl * p,* r,** A; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for(i = 0; i < n; i++) A[i] = NULL; // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi p = new slistEl; // Tworzymy nowy element p->v = v2; // Numerujemy go jako v2 p->next = A[v1]; // Dodajemy go na początek listy A[v1] A[v1] = p; p = new slistEl; // Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1; p->next = A[v2]; A[v2] = p; } if(isCyclic(n,A)) cout << "CYCLIC GRAPH"; else cout << "ACYCLIC GRAPH"; cout << endl; // Usuwamy tablicę list sąsiedztwa for(i = 0; i < n; i++) { p = A[i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; return 0; } |
|
Free Basic | |
' Badanie cykliczności niespójnego grafu nieskierowanego ' Data: 14.12.2013 ' (C)2013 mgr Jerzy Wałaszek '-------------------------------------------------------- ' Typy dla dynamicznej tablicy list sąsiedztwa i stosu Type slistEl next As slistEl Ptr v As Integer End Type Type stack Private: S As slistEl Ptr ' lista zawierająca stos Public: Declare Constructor() Declare Destructor() Declare Function empty() As Integer Declare Function top As Integer Declare Sub push(ByVal v As Integer) Declare Sub pop() End Type '--------------------- ' Metody obiektu stack '--------------------- ' Konstruktor '------------ Constructor stack() S = 0 End Constructor ' Destruktor '----------- Destructor stack() While S pop() Wend End Destructor ' Sprawdza, czy stos jest pusty '------------------------------ Function stack.empty() As Integer If S = 0 Then Return 1 Return 0 End Function ' Zwraca szczyt stosu. '------------------------------ Function stack.top() As Integer top = S->v End Function ' Zapisuje na stos '----------------- Sub stack.push(ByVal v As Integer) Dim e As slistEl Ptr e = New slistEl e->v = v e->Next = S S = e End Sub ' Usuwa ze stosu '--------------- Sub stack.pop() Dim e As slistEl Ptr If S Then e = S S = S->Next Delete e End If End Sub ' Funkcja bada cykliczność składowej grafu '----------------------------------------- Function isComponentCyclic(ByVal G As slistEl Ptr Ptr, ByVal v As Integer, ByVal visited As Integer Ptr) As Integer Dim As stack S ' Stos Dim As slistEl Ptr p ' Wskaźnik elementu listy Dim As Integer w,z ' Zmienne pomocnicze S.push(v): S.push(-1) ' Na stos wierzchołek startowy i -1 visited[v] = 1 ' Wierzchołek oznaczamy jako odwiedzony While S.empty() = 0 ' W pętli przechodzimy graf za pomocą DFS w = S.top(): S.pop() ' Pobieramy ze stosu wierzchołek z którego przyszliśmy v = S.top(): S.pop() ' oraz wierzchołek bieżący p = G[v] While p ' Przeglądamy jego listę sąsiadów z = p->v ' Numer sąsiada If visited[z] = 0 Then S.push(z): S.push(v) ' Sąsiada nieodwiedzonego umieszczamy na stosie visited[z] = 1 ElseIf z <> w Then ' Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem ' z którego przyszliśmy, to odkryliśmy cykl Return 1 ' Kończymy z wynikiem true EndIf p = p->Next Wend Wend Return 0 ' W grafie nie ma cykli. Kończymy z wynikiem false End Function ' Funkcja bada cykliczność grafu '------------------------------- Function isCyclic(ByVal n As Integer, ByVal G As slistEl Ptr Ptr) As Integer Dim As Integer i Dim As Integer ptr visited visited = new Integer [n] ' Tworzymy tablicę odwiedzin For i = 0 To n - 1 visited[i] = 0 ' Tablicę zerujemy Next For i = 0 To n - 1 ' Szukamy wierzchołka startowego If (visited[i] = 0) AndAlso (isComponentCyclic(G,i,visited) = 1) Then Delete [] visited Return 1 ' Cykl znaleziony, kończymy z true End If Next Delete [] visited Return 0 ' Graf nie posiada cyklu, kończymy z false End Function ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer n,m,i,v1,v2 Dim As slistEl Ptr p,r Dim As slistEl Ptr Ptr A Open Cons For Input As #1 Input #1,n,m ' Czytamy liczbę wierzchołków i krawędzi A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa ' Tablicę wypełniamy pustymi listami For i = 0 To n - 1 A[i] = 0 Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m -1 Input #1,v1,v2 ' Wierzchołek startowy i końcowy krawędzi p = new slistEl ' Tworzymy nowy element p->v = v2 ' Numerujemy go jako v2 p->next = A[v1] ' Dodajemy go na początek listy A[v1] A[v1] = p p = new slistEl ' Krawędź w drugą stronę, bo graf jest nieskierowany p->v = v1 p->next = A[v2] A[v2] = p Next Close #1 If isCyclic(n,A) Then Print "CYCLIC GRAPH" Else Print "ACYCLIC GRAPH" EndIf ' Usuwamy tablicę list sąsiedztwa For i = 0 To n - 1 p = A[i] While p r = p p = p->Next Delete r Wend Next Delete [] A End |
|
Wynik | |
12 11 0 1 1 8 2 3 2 5 3 7 4 9 5 8 5 10 6 9 6 11 7 10 CYCLIC GRAPH |
12 10 0 1 1 8 2 3 2 5 4 9 5 8 5 10 6 9 6 11 7 10 ACYCLIC GRAPH |
Jeśli przejście DFS wyruszy od wierzchołka 0, to dotrze do wierzchołka 3 dwoma drogami (niebieską i czerwoną). Jeśli pierwsza będzie droga niebieska, to DFS ustawi wierzchołek 3 jako odwiedzony. Następnie wyruszy drogą czerwoną i w wierzchołku 2 stwierdzi, że istnieje krawędź do już odwiedzonego wcześniej wierzchołka 3. Wg kryterium dla grafu nieskierowanego oznacza to cykl. Jak widzimy, tutaj to kryterium zawodzi, ponieważ cykl nie istnieje. Wniosek jest tylko jeden: dla grafu skierowanego musimy przyjąć inne kryterium wykrywania cyklu.
Umówmy się, że wierzchołki grafu będą mogły znajdować się w trzech stanach pamiętanych przez tablicę odwiedzin:
W grafie skierowanym cykl istnieje tylko wtedy, gdy krawędź wiedzie do wierzchołka przetwarzanego (szarego). Wierzchołki już przetworzone nie mogą tworzyć cyklu (gdyby tak było, to algorytm znalazł by już ten cykl wcześniej i zakończył swoje działanie, nieprawdaż?). Prześledźmy to na prostym przykładzie.
![]() |
Mamy dany graf skierowany. Umówmy się, że DFS będzie go
przechodzić wg kolejnych numerów wierzchołków. Początkowo wszystkie wierzchołki są białe. |
![]() |
Przejście DFS rozpoczynamy od wierzchołka 0. Zmieniamy jego kolor na szary (oznaczający wierzchołek w trakcie przetwarzania). Posiada on trzech sąsiadów: wierzchołki 1, 2 i 3, które odwiedzamy rekurencyjnie w tej kolejności. |
![]() |
Przechodzimy do wierzchołka 1. Zmieniamy jego kolor na szary. Wierzchołek posiada tylko jednego sąsiada: wierzchołek nr 2. |
![]() |
Przechodzimy do wierzchołka 2. Ponieważ wierzchołek ten nie posiada dalszych sąsiadów, zmieniamy jego kolor na czarny (oznaczający zakończenie przetwarzania wierzchołka). |
![]() |
Wracamy do wierzchołka 1. Wierzchołek nie posiada dalszych sąsiadów. Zmieniamy jego kolor na czarny. |
![]() |
Wracamy do wierzchołka 0. Posiada on wciąż dwóch sąsiadów do
zbadania: wierzchołki 2 i 3. Do wierzchołka 2 nie przechodzimy, ponieważ ma kolor czarny (odwiedzamy tylko wierzchołki białe, a napotkanie wierzchołka szarego sygnalizuje cykl). Zatem kolejnym do odwiedzenia wierzchołkiem będzie wierzchołek 3. |
![]() |
Idziemy do wierzchołka 3. Kolorujemy go na szaro. Kolejnym do odwiedzenia sąsiadem jest wierzchołek 4. |
![]() |
Idziemy do wierzchołka 4. Kolorujemy go na szaro. Następnym do odwiedzenia jest wierzchołek 5. |
![]() |
Jesteśmy w wierzchołku 5. Kolorujemy go na szaro. Wykrywamy, że sąsiad 3 jest szary. Oznacza to istnienie cyklu. Kończymy algorytm z wynikiem pozytywnym – graf jest cykliczny. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje |
v | – | numer wierzchołka startowego, v
![]() |
visited | – | n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych |
false – graf nie jest cykliczny
u | – | wierzchołek sąsiedni, u
![]() |
K01: | vsited[v] ← szary | ; oznaczamy bieżący wierzchołek jako szary |
K02: | Dla każdego sąsiada u wierzchołka v wykonuj K03...K05 | |
K03: | Jeśli visited[u] = czarny, to następny obieg pętli K02 | ; wierzchołki przetworzone ignorujemy |
K04: | Jeśli visited[u] = szary, to zakończ z wynikiem true | ; cykl znaleziony, kończymy |
K05: | Jeśli isGraphCyclic(graf,u,visited) = true, to zakończ z wynikiem true | ; wywołanie rekurencyjne dla sąsiada u |
K06: | visited[v] ← czarny | ; wierzchołek przetworzony, ustawiamy kolor czarny |
K07: | Zakończ z wynikiem false | ; nie było cyklu |
n | – | liczba wierzchołków w grafie, n
![]() |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje |
false – graf nie jest cykliczny
i | – | wierzchołek startowy, i
![]() |
visited | – | n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych |
K01: | Utwórz n elementową tablicę visited | |
K02: | Ustaw wszystkie elementy tablicy visited na biało | |
K03: | Dla i = 0,1,...,n-1, wykonuj K04..K05 | ; szukamy pierwszego nieodwiedzonego jeszcze wierzchołka |
K04: | Jeśli visited[i] ≠ biały, to następny obieg pętli K3 | ; pomijamy wierzchołki już przetworzone |
K05: | Jeśli isGraphCyclic(graf,i,visited) = true, to zakończ z wynikiem true | ; sprawdzamy cykliczność składowej zawierającej znaleziony wierzchołek |
K06: | Zakończ z wynikiem false |
Kolory możemy kodować liczbami lub nawet znakami (znaki ASCII zajmują 1 bajt pamięci) : 'b', 0 (biały); 's', 1 (szary) i 'c', 2 (czarny).
Ważne: 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. |
Przykładowe dane dla programu:
Cykliczny graf skierowany
|
6 7 0 1 0 2 0 3 1 2 3 4 4 5 5 3 |
Niecykliczny graf skierowany
|
6 7 0 1 0 2 0 3 1 2 3 4 3 5 4 5 |
Lazarus | |
// Badanie cykliczności grafu skierowanego // Data: 19.12.2013 // (C)2013 mgr Jerzy Wałaszek //---------------------------------------- program project1; // Typy dla dynamicznej tablicy list sąsiedztwa type PslistEl = ^slistEl; slistEl = record next : PslistEl; v : integer; end; TList = array of PslistEl; // Funkcje badające cykliczność grafu //----------------------------------- function isGraphCyclic(var G : TList; v : integer; var visited : array of char) : boolean; var p : PslistEl; // Wskaźnik elementu listy u : integer; begin visited[v] := 'G'; // Kolorujemy wierzchołek na szaro p := G[v]; // Sprawdzamy kolejnych sąsiadów while p <> nil do begin u := p^.v; // u <-- numer sąsiada if visited[u] = 'G' then Exit(true); // Sąsiad szary - mamy cykl. przerywamy if (visited[u] = 'W') and isGraphCyclic(G,u,visited) then Exit(true); // Wywołanie rekurencyjne p := p^.next; end; visited[v] := 'B'; // Kolorujemy wierzchołek na czarno Exit(false); end; function isCyclic(n : integer; var G : Tlist) : boolean; var i : integer; visited : array of char; begin SetLength(visited,n); // Tworzymy tablicę odwiedzin for i := 0 to n - 1 do visited[i] := 'W'; // Tablicę zerujemy for i := 0 to n - 1 do if (visited[i] = 'W') and isGraphCyclic(G,i,visited) then Exit(true); Exit(false); end; // ********************** // *** Program główny *** // ********************** var n,m,i,v1,v2 : integer; p,r : PslistEl; A : TList; begin read(n,m); // Czytamy liczbę wierzchołków i krawędzi SetLength(A,n); // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for i := 0 to n - 1 do A[i] := nil; // Odczytujemy kolejne definicje krawędzi for i := 0 to m - 1 do begin read(v1,v2); // Wierzchołek startowy i końcowy krawędzi new(p); // Tworzymy nowy element p^.v := v2; // Numerujemy go jako v2 p^.next := A[v1]; // Dodajemy go na początek listy A[v1] A[v1] := p; end; if isCyclic(n,A) then writeln('CYCLIC GRAPH') else writeln('ACYCLIC GRAPH'); // Usuwamy tablicę list sąsiedztwa for i := 0 to n - 1 do begin p := A[i]; while p <> nil do begin r := p; p := p^.next; dispose(r); end; end; SetLength(A,0); end. |
|
Code::Blocks | |
// Badanie cykliczności grafu skierowanego // Data: 19.12.2013 // (C)2013 mgr Jerzy Wałaszek //---------------------------------------- #include <iostream> using namespace std; // Typy dla dynamicznej tablicy list sąsiedztwa struct slistEl { slistEl * next; int v; }; // Funkcje badające cykliczność grafu //----------------------------------- bool isGraphCyclic(slistEl ** G, int v, char * visited) { slistEl * p; // Wskaźnik elementu listy int u; visited[v] = 'G'; // Kolorujemy wierzchołek na szaro p = G[v]; // Sprawdzamy kolejnych sąsiadów while(p) { u = p->v; // u <-- numer sąsiada if(visited[u] == 'G') return true; // Sąsiad szary - mamy cykl. przerywamy if((visited[u] == 'W') && isGraphCyclic(G,u,visited)) return true; // Wywołanie rekurencyjne p = p->next; } visited[v] = 'B'; // Kolorujemy wierzchołek na czarno return false; } bool isCyclic(int n, slistEl ** G) { int i; char * visited; visited = new char[n]; // Tworzymy tablicę odwiedzin for(i = 0; i < n; i++) visited[i] = 'W'; // Tablicę zerujemy for(i = 0; i < n; i++) if((visited[i] = 'W') && isGraphCyclic(G,i,visited)) return true; return false; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { int n,m,i,v1,v2; slistEl * p,* r,** A; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa // Tablice wypełniamy pustymi listami for(i = 0; i < n; i++) A[i] = NULL; // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi p = new slistEl; // Tworzymy nowy element p->v = v2; // Numerujemy go jako v2 p->next = A[v1]; // Dodajemy go na początek listy A[v1] A[v1] = p; } if(isCyclic(n,A)) cout << "CYCLIC GRAPH"; else cout << "ACYCLIC GRAPH"; cout << endl; // Usuwamy tablicę list sąsiedztwa for(i = 0; i < n; i++) { p = A[i]; while(p) { r = p; p = p->next; delete r; } } delete [] A; return 0; } |
|
Free Basic | |
' Badanie cykliczności grafu skierowanego ' Data: 19.12.2013 ' (C)2013 mgr Jerzy Wałaszek '---------------------------------------- ' Typy dla dynamicznej tablicy list sąsiedztwa Type slistEl next As slistEl Ptr v As Integer End Type ' Funkcje badające cykliczność grafu '----------------------------------- Const WHITE = 0 Const GRAY = 1 Const BLACK = 2 Function isGraphCyclic(ByVal G As slistEl Ptr Ptr,_ ByVal v As Integer, _ ByVal visited As Byte Ptr) As Integer Dim As slistEl ptr p ' Wskaźnik elementu listy Dim As Integer u visited[v] = GRAY ' Kolorujemy wierzchołek na szaro p = G[v] ' Sprawdzamy kolejnych sąsiadów While p u = p->v ' u <-- numer sąsiada If visited[u] = GRAY Then Return 1 ' Sąsiad szary - mamy cykl. przerywamy If (visited[u] = WHITE) AndAlso _ (isGraphCyclic(G,u,visited) = 1) Then Return 1 ' Wywołanie rekurencyjne p = p->Next Wend visited[v] = BLACK ' Kolorujemy wierzchołek na czarno Return 0 End Function Function isCyclic(ByVal n As integer, ByVal G As slistEl Ptr Ptr) As Integer Dim As Integer i Dim As Byte Ptr visited visited = New Byte[n] ' Tworzymy tablicę odwiedzin For i = 0 To n - 1 visited[i] = WHITE ' Tablicę zerujemy Next For i = 0 To n - 1 If (visited[i] = WHITE) AndAlso _ (isGraphCyclic(G,i,visited) = 1) Then Return 1 Next Return 0 End Function ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer n,m,i,v1,v2 Dim As slistEl Ptr p,r Dim As slistEl Ptr Ptr A Open Cons For Input As #1 Input #1,n,m ' Czytamy liczbę wierzchołków i krawędzi A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa ' Tablicę wypełniamy pustymi listami For i = 0 To n - 1 A[i] = 0 Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m -1 Input #1,v1,v2 ' Wierzchołek startowy i końcowy krawędzi p = new slistEl ' Tworzymy nowy element p->v = v2 ' Numerujemy go jako v2 p->next = A[v1] ' Dodajemy go na początek listy A[v1] A[v1] = p Next Close #1 If isCyclic(n,A) Then Print "CYCLIC GRAPH" Else Print "ACYCLIC GRAPH" EndIf ' Usuwamy tablicę list sąsiedztwa For i = 0 To n - 1 p = A[i] While p r = p p = p->Next Delete r Wend Next Delete [] A End |
|
Wynik | |
6 7 0 1 0 2 0 3 1 2 3 4 4 5 5 3 CYCLIC GRAPH |
6 7 0 1 0 2 0 3 1 2 3 4 3 5 4 5 ACYCLIC GRAPH |
![]() | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe