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 |
ProblemNależy 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 ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
S | – | stos liczb całkowitych. |
w, v, z | – | wierzchołki robocze, w, v, z ∈ C. |
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 kroki 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 kroki 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 |
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ę spójnego grafu nieskierowanego i sprawdza, czy jest on grafem cyklicznym. Jeśli tak, to wypisuje tekst "CYCLIC GRAPH". W przeciwnym razie wypisuje tekst "ACYCLIC GRAPH". |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// 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. |
C++// 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; } |
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 |
Jeśli graf jest niespójny, to składa się z kilku spójnych składowych. W takim przypadku test na cykliczność wykonujemy dla każdej spójnej składowej. Zasada jest następująca:
Tablicę visited tworzymy poza głównym algorytmem i zerujemy ją
(algorytm główny tego nie robi ). W osobnej zmiennej zapamiętujemy numer
wierzchołka startowego ( na początku będzie to 0 ). Następnie uruchamiamy
poprzednio opisany algorytm, przekazując do niego numer wierzchołka startowego
oraz tablicę visited. Algorytm odwiedza za pomocą DFS wierzchołki spójnej
składowej, do której należy wierzchołek startowy. Jednocześnie w tablicy visited
są odnotowane wierzchołki odwiedzone. Jeśli algorytm ten wykryje cykl, to zwraca
true. W takim przypadku kończymy i również zwracamy true, ponieważ graf jest
cykliczny. Jeśli algorytm zwróci false, to przeszukana spójna składowa grafu nie
zawiera cyklu. W takim przypadku musimy przeszukać kolejną spójną składową. W
tablicy visited szukamy od zapamiętanej pozycji startowej pierwszej komórki,
która zawiera wartość false. Odpowiada ona wierzchołkowi, którego algorytm
testowania cykliczności nie odwiedził, a zatem wierzchołek ten leży w innej
składowej grafu. Uruchamiamy ponownie całą procedurę, przekazując do algorytmu
cykliczności numer znalezionego wierzchołka oraz tablicę visited. Jeśli w
tablicy visited nie będzie już komórek o wartości false, to cały graf jest
przeszukany i nie zawiera cyklu. Kończymy zwracając false.
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
v | – | numer wierzchołka startowego, v ∈ C. |
visited | – | n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych. |
S | – | stos liczb całkowitych. |
w, z | – | wierzchołki robocze, w, v, z ∈ C. |
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 kroki 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 kroki 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 ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
i | – | wierzchołek startowy, i ∈ C. |
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 kroki 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 |
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ę dowolnego grafu nieskierowanego i sprawdza, czy jest on grafem cyklicznym. Jeśli tak, to wypisuje tekst "CYCLIC GRAPH". W przeciwnym razie wypisuje tekst "ACYCLIC GRAPH". |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// 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. |
C++// 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; } |
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 |
Przy grafie skierowanym postępujemy podobnie jak przy grafie niespójnym. Chodzi o to, że z uwagi na kierunkowość krawędzi przejście DFS od wybranego wierzchołka nie gwarantuje nam odwiedzenia wszystkich wierzchołków w grafie, a te nieodwiedzone wierzchołki mogą tworzyć cykle. Istnieje również drugi problem: w grafie skierowanym DFS może ponownie odwiedzać określony wierzchołek, a mimo to nie będzie cyklu. Przyjrzyjmy się poniższemu rysunkowi:
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 ∈ C. |
visited | – | n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych. |
u | – | wierzchołek sąsiedni, u ∈ C. |
K01: | vsited [ v ] ← szary | oznaczamy bieżący wierzchołek jako szary |
K02: | Dla każdego sąsiada u
wierzchołka
v : wykonuj kroki 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 ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. |
i | – | wierzchołek startowy, i ∈ C. |
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 kroki 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 ).
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ę dowolnego grafu skierowanego i sprawdza, czy jest on grafem cyklicznym. Jeśli tak, to wypisuje tekst "CYCLIC GRAPH". W przeciwnym razie wypisuje tekst "ACYCLIC GRAPH". |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// 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. |
C++// 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; } |
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 |
![]() |
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.