Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Cykliczność grafu

SPIS TREŚCI
Podrozdziały

Problem

Należy zbadać, czy dany graf jest cykliczny.

Rozwiązanie dla spójnego grafu nieskierowanego

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.

obrazek Rozpoczynamy przejście DFS od wierzchołka 0.
obrazek 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 ).
obrazek Przechodzimy do wierzchołka 2. Wierzchołek 1 będzie ignorowany, ponieważ przyszliśmy z niego.
obrazek Przechodzimy do wierzchołka 3. Wierzchołek 2 będzie ignorowany.
obrazek 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 ).
obrazek Wierzchołek 2 nie posiada dalszych sąsiadów, wracamy do wierzchołka 1. Kontynuujemy przeglądanie dalszych sąsiadów wierzchołka 1.
obrazek Przechodzimy do wierzchołka 4. Wierzchołek 1 ignorujemy, ponieważ przyszliśmy z niego.
obrazek Przechodzimy do wierzchołka 5.
obrazek 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.

Algorytm sprawdzania cykliczności spójnego grafu nieskierowanego

Funkcja isCyclic ( n, graf )

Wejście:

n  –  liczba wierzchołków w grafie, n  ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.
Zmienne pomocnicze:
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.

Lista kroków:

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

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję 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 ):
Graf cykliczny
obrazek		   6 6
0 1
1 2 1 4 1 5
2 3
4 5		     Graf niecykliczny (drzewo )
obrazek		   6 5
0 1
1 2 1 4
2 3
4 5
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
Na początek:  podrozdziału   strony 

Rozwiązanie dla niespójnego grafu nieskierowanego

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.

Algorytm sprawdzania cykliczności niespójnego grafu nieskierowanego

Funkcja isComponentCyclic ( graf, v, visited )

Wejście:

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.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.
Zmienne pomocnicze:
S  –  stos liczb całkowitych.
w, z  –  wierzchołki robocze, w, v, z ∈ C.

Lista kroków:

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

Funkcja isCyclic ( n, graf )

Wejście:

n  –  liczba wierzchołków w grafie, n ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.
Zmienne pomocnicze:
i  –  wierzchołek startowy, i ∈ C.
visited  –  n  elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych.

Lista kroków:

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  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję 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 ):
Niespójny graf cykliczny

obrazek		        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

obrazek		        12 10
0 1
1 8
2 3 2 5
4 9
5 8 5 10
6 9 6 11
7 10
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
Na początek:  podrozdziału   strony 

Rozwiązanie dla grafu skierowanego

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:

obrazek

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.

obrazek 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.
obrazek 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.
obrazek Przechodzimy do wierzchołka 1. Zmieniamy jego kolor na szary. Wierzchołek posiada tylko jednego sąsiada: wierzchołek nr 2.
obrazek 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 ).
obrazek  Wracamy do wierzchołka 1. Wierzchołek nie posiada dalszych sąsiadów. Zmieniamy jego kolor na czarny.
obrazek 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.
obrazek Idziemy do wierzchołka 3. Kolorujemy go na szaro. Kolejnym do odwiedzenia sąsiadem jest wierzchołek 4.
obrazek Idziemy do wierzchołka 4. Kolorujemy go na szaro. Następnym do odwiedzenia jest wierzchołek 5.
obrazek 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.

Algorytm sprawdzania cykliczności grafu skierowanego

Algorytm rekurencyjnej funkcji isGraphCyclic

Wejście:

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.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.
Zmienne pomocnicze:
u  –  wierzchołek sąsiedni, u ∈ C.

Lista kroków:

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

Algorytm funkcji isCyclic ( n, graf )

Wejście:

n  –  liczba wierzchołków w grafie, n ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.
Zmienne pomocnicze:
i  –  wierzchołek startowy, i ∈ C.
visited  –  n  elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych.

Lista kroków:

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 ).

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję 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 ):
Cykliczny graf skierowany
obrazek		        6 7
0 1 0 2 0 3
1 2
3 4
4 5
5 3		        Niecykliczny graf skierowany
obrazek		        6 7
0 1 0 2 0 3
1 2
3 4 3 5
4 5
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
Na początek:  podrozdziału   strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 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.