Algorytmy i Struktury Danych - Cykliczność grafu

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.

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.

Elementy pomocnicze:

S : stos liczb całkowitych.
w,v,z : wierzchołki robocze; w,v,z ∈ C.
vs : n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych.

Lista kroków:

K01: Utwórz n elementową tablicę vs
K02: Ustaw wszystkie elementy tablicy vs 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: vs[0] ← true ; wierzchołek zaznaczamy jako odwiedzony
K07: Dopóki S.empty() = false, ; w pętli przechodzimy graf algorytmem DFS
     wykonuj kroki K08…K12
K08:   w ← S.top() ; w – wierzchołek, z którego przyszliśmy
       S.pop()
K09:   v ← S.top() ; v – wierzchołek bieżący
       S.pop()
K10:   Dla każdego sąsiada z wierzchołka v:
       wykonuj kroki K11…K12
K11:   Jeśli vs[z] = false, ; jeśli sąsiad nie jest odwiedzony,
       to: ; to umieszczamy go na stosie wraz z numerem bieżącego wierzchołka
         S.push(z)
         S.push(v)
         vs[z] ← true
         Następny obieg pętli K10
K12:   Jeśli z ≠ w, ; trafiliśmy na odwiedzony wierzchołek,
       to zakończ z wynikiem true ; 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		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

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu
// obiektowego Stack
//-----------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;

  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
  if S <> NIL then
    top := S^.v
  else
    top := -MAXINT;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
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
  // Stos
  S : Stack;
  // Tablica odwiedzin
  vs : array of boolean;
  // Wskaźnik elementu listy
  p : PSLel;
  // Zmienne pomocnicze
  w, v, z, i : integer;
begin
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // i zerujemy ją
    vs[i] := false;
  // Tworzymy pusty stos
  S.init;
  // Na stos wierzchołek
  // startowy 0 i -1
  S.push(0); S.push(-1);
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[0] := true;
  // W pętli przechodzimy
  // graf za pomocą DFS
  while S.empty = false do
  begin
    // Pobieramy ze stosu
    // wierzchołek, z którego
    // przyszliśmy
    w := S.top; S.pop;
    // oraz wierzchołek bieżący
    v := S.top; S.pop;
    // Przeglądamy jego
    // listę sąsiadów
    p := G[v];
    while p <> nil do
    begin
      // Numer sąsiada
      z := p^.v;
      if not vs[z] then
      begin
        // Sąsiada
        // nieodwiedzonego
        // umieszczamy na stosie
        S.push(z); S.push(v);
        // Oznaczamy go
        // jako odwiedzonego
        vs[z] := true;
      end
      // Jeśli sąsiad jest
      // odwiedzony i nie
      // jest wierzchołkiem,
      else if z <> w then
      // z którego przyszliśmy,
      // to odkryliśmy cykl
      begin
        // Usuwamy elementy
        // pomocnicze
        SetLength(vs, 0);
        S.destroy;
        // Kończymy
        // z wynikiem true
        Exit(true);
      end;
      p := p^.next;
    end;
  end;
  // W grafie nie ma cykli.
  SetLength(vs, 0);
  S.destroy;
  // Kończymy z wynikiem false
  Exit(false);
end;

// **********************
// *** Program główny ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;
  A : TList;

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
    // Krawędź w drugą stronę,
    // bo graf jest
    // nieskierowany
    new(p);
    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 SLel
{
  SLel * next;
  int v;
};

const int MAXINT = 2147483647;

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

  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 = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S) return S->v;
  return -MAXINT;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja bada cykliczność grafu
//-------------------------------
bool isCyclic(int n, SLel ** G)
{
  // Stos
  Stack S;
  // Tablica odwiedzin
  bool * vs;
  // Wskaźnik elementu listy
  SLel * p;
  // Zmienne pomocnicze
  int w, v, z, i;

  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  for(i = 0; i < n; i++)
    // i zerujemy ją
    vs[i] = false;
  // Na stos wierzchołek
  // startowy i -1
  S.push(0); S.push(-1);
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[0] = true;
  // W pętli przechodzimy
  // graf za pomocą DFS
  while(!S.empty())
  {
    // Pobieramy ze stosu
    // wierzchołek,
    // z którego przyszliśmy
    w = S.top(); S.pop();
    // oraz wierzchołek bieżący
    v = S.top(); S.pop();
    // Przeglądamy jego
    // listę sąsiadów
    for(p = G[v]; p; p = p->next)
    {
      // Numer sąsiada
      z = p->v;
      if(!vs[z])
      {
        // Sąsiada nieodwiedzonego
        // umieszczamy na stosie
        S.push(z); S.push(v);
        // Oznaczamy go
        // jako odwiedzonego
        vs[z] = true;
      }
      // Jeśli sąsiad jest odwiedzony
      // i nie jest wierzchołkiem,
      else if(z != w)
      // z którego przyszliśmy,
      // to odkryliśmy cykl
      {
        delete [] vs;
        // Kończymy z wynikiem true
        return true;
      }
    }
  }
  // W grafie nie ma cykli.
  delete [] vs;
  // Kończymy z wynikiem false
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel * p, * r, ** A;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tablice wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    A[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = A[v1];
    A[v1] = p;
    // Krawędź w drugą stronę,
    // bo graf jest nieskierowany
    p = new SLel;
    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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr 
  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

Const MAXINT = 2147483647

'---------------------
' 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
  If S = 0 Then
    top = MAXINT
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->Next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S <> 0 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 SLel Ptr Ptr) _
                          As Integer
  ' Stos
  Dim As Stack S
  ' Tablica odwiedzin
  Dim As Integer ptr vs
  ' Wskaźnik elementu listy
  Dim As SLel Ptr p
  ' Elementy pomocnicze
  Dim As Integer w, v, z, i

  ' Tworzymy tablicę odwiedzin
  vs = new Integer [n]
  For i = 0 To n-1
    ' i zerujemy ją
    vs[i] = 0
  Next
  ' Na stos wierzchołek startowy i -1
  S.push(0): S.push(-1)
  ' Oznaczamy wierzchołek jako odwiedzony
  vs[0] = 1
  ' W pętli przechodzimy graf za pomocą DFS
  While S.empty() = 0
    ' Pobieramy ze stosu wierzchołek,
    ' z którego przyszliśmy
    w = S.top(): S.pop()
    ' oraz wierzchołek bieżący
    v = S.top(): S.pop()
    p = G[v]
    ' Przeglądamy jego listę sąsiadów
    While p <> 0
      ' Numer sąsiada
      z = p->v
      If vs[z] = 0 Then
        ' Sąsiada nieodwiedzonego
        ' umieszczamy na stosie
        S.push(z): S.push(v)
        ' Oznaczamy go jako odwiedzonego
        vs[z] = 1
      ' Jeśli sąsiad jest odwiedzony
      ' i nie jest wierzchołkiem,
      ElseIf z <> w Then
        ' z którego przyszliśmy,
        ' to odkryliśmy cykl
        Delete [] vs
        ' Kończymy z wynikiem true
        Return 1
      EndIf
      p = p->next
    Wend
  Wend
  ' W grafie nie ma cykli.
  Delete [] vs
  ' Kończymy z wynikiem false
  Return 0
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
  ' Krawędź w drugą stronę,
  ' bo graf jest nieskierowany
  p = new SLel
  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

Python (dodatek)

# Badanie cykliczności
# spójnego grafu nieskierowanego
# Data: 23.01.2025
# (C)2025 mgr Jerzy Wałaszek
#-------------------------------

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

MAXINT = 2147483647

class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza, czy stos jest pusty
    def empty(self):
        if not self.s:
            return True
        else:
            return False


    # Zwraca szczyt stosu.
    def top(self):
        global MAXINT
        if not self.s:
            return MAXINT
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Funkcja bada cykliczność grafu
def is_cyclic(n, g):
    # Tworzymy tablicę odwiedzin
    vs = [False] * n
    # Tworzymy stos
    s = Stack()
    # Na stos wierzchołek startowy i -1
    s.push(0)
    s.push(-1)
    # Oznaczamy wierzchołek
    # jako odwiedzony
    vs[0] = True
    # W pętli przechodzimy graf
    # za pomocą DFS
    while not s.empty():
        # Pobieramy ze stosu wierzchołek,
        # z którego przyszliśmy
        w = s.top()
        s.pop()
        # oraz wierzchołek bieżący
        v = s.top()
        s.pop()
        p = g[v]
        # Przeglądamy jego listę sąsiadów
        while p:
            # Numer sąsiada
            z = p.v
            if not vs[z]:
                # Sąsiada nieodwiedzonego
                # umieszczamy na stosie
                s.push(z)
                s.push(v)
                # Oznaczamy go
                # jako odwiedzonego
                vs[z] = True
            # Jeśli sąsiad jest odwiedzony
            # i nie jest wierzchołkiem,
            elif z != w:
                # z którego przyszliśmy,
                # to odkryliśmy cykl
                del vs
                # Kończymy z wynikiem true
                return True
            p = p.next
    # W grafie nie ma cykli.
    del vs
    # Kończymy z wynikiem false
    return False

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek listy a[v1]
    p.next = a[v1]
    a[v1] = p
    # Krawędź w drugą stronę,
    # bo graf jest nieskierowany
    p = SLel()
    p.v = v1
    p.next = a[v2]
    a[v2] = p
if is_cyclic(n, a):
    print("CYCLIC GRAPH")
else:
    print("ACYCLIC GRAPH")
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

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

do podrozdziału do strony

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ę vs 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ę vs. Algorytm odwiedza za pomocą DFS wierzchołki spójnej składowej, do której należy wierzchołek startowy. Jednocześnie w tablicy vs 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 vs 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ę vs. Jeśli w tablicy vs 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 isCCyclic(graf,v,vs)

Wejście:

graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : numer wierzchołka startowego; v ∈ C.
vs : n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych.

Wyjście:

true – graf jest cykliczny.
false – graf nie jest cykliczny.

Elementy pomocnicze:

S : stos liczb całkowitych.
w,v,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: vs[v] ← true ; wierzchołek oznaczamy jako odwiedzony
K04: Dopóki S.empty() = false, ; w pętli przechodzimy graf algorytmem DFS
     wykonuj kroki K05…K09
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 vs[z] = false, ; jeśli sąsiad nie jest odwiedzony,
         to: ; to umieszczamy go na stosie wraz z numerem bieżącego wierzchołka
         S.push(z)
         S.push(v)
         vs[z] ← true
         Następny obieg pętli K07
K09:   Jeśli z ≠ w, ; trafiliśmy na odwiedzony wierzchołek,
       to zakończ z wynikiem true ; 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.

Elementy pomocnicze:

i : wierzchołek startowy; i ∈ C.
vs : n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych.

Lista kroków:

K01: Utwórz n elementową tablicę vs
K02: Ustaw wszystkie elementy tablicy vs na false
K03: Dla i = 0, 1, …, n-1, ; szukamy pierwszego nieodwiedzonego
     wykonuj kroki K04..K05 ; jeszcze wierzchołka
K04:   Jeśli vs[i] = true,
       to następny obieg pętli K3
K05:   Jeśli isCCyclic(graf,i,vs) = true, ; sprawdzamy cykliczność
       to zakończ z wynikiem true ; 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		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

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    S : PSLel;  // 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
  if S <> nil then
    top := S^.v
  else
    top := -MAXINT;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push (v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e : PSLel;
begin
  if S <> nil then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Funkcja bada cykliczność składowej grafu
//-----------------------------------------
function isCCyclic(var G : TList;
                       v : integer;
             var vs : array of boolean)
                         : boolean;
var
  // Stos
  S : Stack;
  // Wskaźnik elementu listy
  p : PSLel;
  // Elementy pomocnicze
  w, z : integer;

begin
  // Tworzymy pusty stos
  S.init;
  // Na stos wierzchołek startowy i -1
  S.push(v); S.push(-1);
  // Oznaczamy wierzchołek
  // startowy jako odwiedzony
  vs[v] := true;
  // W pętli przechodzimy
  // graf za pomocą DFS
  while S.empty = false do
  begin
    // Pobieramy ze stosu wierzchołek
    // z którego przyszliśmy
    w := S.top; S.pop;
    // oraz wierzchołek bieżący
    v := S.top; S.pop;
    // Przeglądamy jego listę sąsiadów
    p := G[v];
    while p <> nil do
    begin
      // Numer sąsiada
      z := p^.v;
      if vs[z] = false then
      begin
        // Sąsiada nieodwiedzonego
        // umieszczamy na stosie
        S.push(z); S.push(v);
        vs[z] := true;
      end
      // Jeśli sąsiad jest odwiedzony
      // i nie jest wierzchołkiem
      else if z <> w then
      // z którego przyszliśmy,
      // to odkryliśmy cykl
      begin
        S.destroy;
        // Kończymy z wynikiem true
        Exit(true);
      end;
      p := p^.next;
    end;
  end;
  S.destroy;
  // Kończymy z wynikiem false
  Exit(false);
end;

// Funkcja bada cykliczność grafu
//-------------------------------
function isCyclic(n : integer;
              var G : Tlist)
                    : boolean;
var
  i : integer;
  vs : array of boolean;
begin
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // Tablicę zerujemy
    vs[i] := false;
  // Szukamy wierzchołka startowego
  for i := 0 to n-1 do
    if (vs[i] = false) and
       (isCCyclic(G,i,vs) = true) then
    begin
      SetLength(vs, 0);
      // Cykl znaleziony, kończymy z true
      Exit(true);
    end;
  SetLength(vs, 0);
  // Graf nie posiada cyklu,
  // kończymy z false
  Exit(false);
end;

// **********************
// *** Program główny ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;
  A : TList;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablicę list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
    // Krawędź w drugą stronę,
    // bo graf jest nieskierowany
    new(p);
    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 SLel
{
  SLel * next;
  int v;
};

const int MAXINT = 2147483647;

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

  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 = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S) return S->v;
  return -MAXINT;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja bada cykliczność
// składowej grafu
//-------------------------
bool isCCyclic(SLel ** G,
               int v,
               bool * vs)
{
  // Stos
  Stack S;
  // Wskaźnik elementu listy
  SLel * p;
  // Elementy pomocnicze
  int w, z;

  // Na stos wierzchołek
  // startowy i -1
  S.push(v); S.push(-1);
  // Wierzchołek startowy
  // oznaczamy jako odwiedzony
  vs[v] = true;
  // W pętli przechodzimy
  // graf za pomocą DFS
  while(!S.empty())
  {
    // Pobieramy ze stosu
    // wierzchołek, z którego
    // przyszliśmy
    w = S.top(); S.pop();
    // oraz wierzchołek bieżący
    v = S.top(); S.pop();
    // Przeglądamy listę sąsiadów
    for(p = G[v]; p; p = p->next)
    {
      // Numer sąsiada
      z = p->v;
      if(!vs[z])
      {
        // Sąsiada nieodwiedzonego
        // umieszczamy na stosie
        S.push(z); S.push(v);
        vs[z] = true;
      }
      // Jeśli sąsiad jest odwiedzony
      // i nie jest wierzchołkiem,
      // z którego przyszliśmy,
      // to odkryliśmy cykl
      else if(z != w)
        // Kończymy z wynikiem true
        return true;
    }
  }
  // Kończymy z wynikiem false
  return false;
}

// Funkcja bada cykliczność grafu
//-------------------------------
bool isCyclic(int n, SLel ** G)
{
  int i;
  bool * vs;

  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  for(i = 0; i < n; i++)
    // Tablicę zerujemy
    vs[i] = false;
  // Szukamy wierzchołka startowego
  for(i = 0; i < n; i++)
    if(!vs[i] &&
       isCCyclic(G,i,vs))
    {
      delete [] vs;
      // Cykl znaleziony,
      // kończymy z true
      return true;
    }
  delete [] vs;
  // Graf nie posiada cyklu,
  // kończymy z false
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel * p, * r, ** A;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tablice wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    A[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go
    // na początek listy A[v1]
    p->next = A[v1];
    A[v1] = p;
    // Krawędź w drugą stronę,
    // bo graf jest nieskierowany
    p = new SLel;
    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 SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr 
  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

Const MAXINT = 2147483647

'---------------------
' 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
  If S = 0 Then
    top = -MAXINT
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v    = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S <> 0 Then
    e = S
    S = S->next
    Delete e
  End If
End Sub

' Funkcja bada cykliczność składowej grafu
'-----------------------------------------
Function isCCyclic(_
    ByVal G As SLel Ptr Ptr, _
    ByVal v As Integer, _
    ByVal vs As Integer Ptr) _
                  As Integer
  Dim As Stack S ' Stos
  ' Wskaźnik elementu listy
  Dim As SLel Ptr p
  ' Elementy pomocnicze
  Dim As Integer w, z

  ' Na stos wierzchołek startowy i -1
  S.push(v): S.push(-1)
  ' Wierzchołek oznaczamy jako odwiedzony
  vs[v] = 1
  ' W pętli przechodzimy graf za pomocą DFS
  While S.empty = 0
    ' Pobieramy ze stosu wierzchołek,
    ' z którego przyszliśmy
    w = S.top: S.pop
    ' oraz wierzchołek bieżący
    v = S.top: S.pop
    p = G[v]
    ' Przeglądamy jego listę sąsiadów
    While p <> 0
      ' Numer sąsiada
      z = p->v
      If vs[z] = 0 Then
        ' Sąsiada nieodwiedzonego
        ' umieszczamy na stosie
        S.push(z): S.push(v)
        vs[z] = 1
      ' Jeśli sąsiad jest odwiedzony
      ' i nie jest wierzchołkiem
      ' z którego przyszliśmy,
      ' to odkryliśmy cykl
      ElseIf z <> w Then
        ' Kończymy z wynikiem true
        Return 1
      End If
      p = p->next
    Wend
  Wend
  ' W grafie nie ma cykli.
  ' Kończymy z wynikiem false
  Return 0                     
End Function

' Funkcja bada cykliczność grafu
'-------------------------------
Function isCyclic(ByVal n As Integer, _
                  ByVal G As SLel Ptr Ptr) _
                          As Integer
  Dim As Integer i
  Dim As Integer ptr vs

  ' Tworzymy tablicę odwiedzin
  vs = new Integer [n]
  For i = 0 To n-1
    ' Tablicę zerujemy
    vs[i] = 0
  Next
  ' Szukamy wierzchołka startowego
  For i = 0 To n-1
    If (vs[i] = 0) AndAlso _
       (isCCyclic(G,i,vs) = 1) Then
      Delete [] vs
      ' Cykl znaleziony, kończymy z true
      Return 1
    End If
  Next
  Delete [] vs
  ' Graf nie posiada cyklu,
  ' kończymy z false
  Return 0
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
  ' Krawędź w drugą stronę,
  ' bo graf jest nieskierowany
  p = new SLel
  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"
End If
' Usuwamy tablicę list sąsiedztwa
For i = 0 To n-1
  p = A[i]
  While p <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] A
End

Python (dodatek)

# Badanie cykliczności
# niespójnego grafu
# nieskierowanego
# Data: 25.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

MAXINT = 2147483647

class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


    # Destruktor
    def __del__(self):
        while self.s:
            self.pop()


    # Sprawdza,
    # czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        global MAXINT
        if not  self.s:
            return -MAXINT
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Funkcja bada cykliczność
# składowej grafu
def is_c_cyclic(g, v, vs):
    # Stos
    s = Stack()
    # Na stos wierzchołek
    # startowy i -1
    s.push(v)
    s.push(-1)
    # Wierzchołek oznaczamy
    # jako odwiedzony
    vs[v] = 1
    # W pętli przechodzimy graf
    # za pomocą DFS
    while not s.empty():
        # Pobieramy ze stosu
        # wierzchołek,
        # z którego przyszliśmy
        w = s.top()
        s.pop()
        # oraz wierzchołek bieżący
        v = s.top()
        s.pop()
        p = g[v]
        # Przeglądamy
        # jego listę sąsiadów
        while p:
            # Numer sąsiada
            z = p.v
            if not vs[z]:
                # Sąsiada
                # nieodwiedzonego
                # umieszczamy
                # na stosie
                s.push(z)
                s.push(v)
                vs[z] = 1
            # Jeśli sąsiad
            # jest odwiedzony
            # i nie jest
            # wierzchołkiem
            # z którego
            # przyszliśmy,
            # to odkryliśmy cykl
            elif z != w:
                # Kończymy
                # z wynikiem true
                return True
            p = p.next
    # W grafie nie ma cykli.
    # Kończymy z wynikiem false
    return False


# Funkcja bada cykliczność grafu
def is_cyclic(n, g):
    # Tworzymy tablicę odwiedzin
    vs = [False] * n
    # Szukamy
    # wierzchołka startowego
    for i in range(n):
        if not vs[i] and \
           is_c_cyclic(g,i,vs):
            del vs
            # Cykl znaleziony,
            # kończymy z true
            return True
    del vs
    # Graf nie posiada cyklu,
    # kończymy z false
    return False


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek
    # listy a[v1]
    p.next = a[v1]
    a[v1] = p
    # Krawędź w drugą stronę,
    # bo graf jest nieskierowany
    p = SLel()
    p.v = v1
    p.next = a[v2]
    a[v2] = p
if is_cyclic(n, a):
    print("CYCLIC GRAPH")
else:
    print("ACYCLIC GRAPH")
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

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

do podrozdziału do strony

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:

Wierzchołek nieodwiedzony (biały).
Wierzchołek przetwarzany (szary) – nie zostali jeszcze odwiedzeni wszyscy sąsiedzi wierzchołka.
Wierzchołek przetworzony (czarny) – DFS zakończyło odwiedziny u wszystkich sąsiadów.

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.

Algorytm sprawdzania cykliczności grafu skierowanego

Algorytm rekurencyjnej funkcji isGCyclic(graf,v,vs)

Wejście:

graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : numer wierzchołka startowego; v ∈ C.
vs : 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.

Elementy 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 vs[u] = czarny, ; wierzchołki przetworzone ignorujemy
       to następny obieg pętli K02
K04:   Jeśli vs[u] = szary, ; cykl znaleziony, kończymy
       to zakończ z wynikiem true
K05:   Jeśli isGCyclic(graf,u,vs) = true, ; wywołanie rekurencyjne dla sąsiada u
       to zakończ z wynikiem true
K06: vs[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.

Elementy pomocnicze:

i : wierzchołek startowy; i ∈ C.
vs : n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych.

Lista kroków:

K01: Utwórz n elementową tablicę vs
K02: Ustaw wszystkie elementy tablicy vs na biało
K03: Dla i = 0, 1, …, n-1, ; szukamy pierwszego
     wykonuj kroki K04..K05 ; nieodwiedzonego jeszcze wierzchołka
K04:  Jeśli vs[i] ≠ biały, ; pomijamy wierzchołki już przetworzone
      to następny obieg pętli K3
K05:  Jeśli isGCyclic(graf,i,vs) = true, ; sprawdzamy cykliczność
      to zakończ z wynikiem true ; 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		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

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

TList = array of PSLel;

// Funkcje badające
// cykliczność grafu
//------------------
function isGCyclic(var G : TList;
                       v : integer;
             var vs : array of char)
                         : boolean;
var
  // Wskaźnik elementu listy
  p : PSLel;
  u : integer;

begin
  // Kolorujemy wierzchołek na szaro
  vs[v] := 'G';
  // Sprawdzamy kolejnych sąsiadów
  p := G[v];
  while p <> nil do
  begin
    // u <-- numer sąsiada
    u := p^.v;
    // Sąsiad szary - mamy cykl.
    // Przerywamy
    if vs[u] = 'G' then
      Exit(true);
    // Wywołanie rekurencyjne
    if (vs[u] = 'W') and
       isGCyclic(G,u,vs) then
      Exit(true);
    p := p^.next;
  end;
  // Kolorujemy wierzchołek
  // na czarno
  vs[v] := 'B';
  Exit(false);
end;

function isCyclic(n : integer;
              var G : Tlist)
                    : boolean;
var
  i : integer;
  vs : array of char;

begin
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // Tablicę zerujemy
    vs[i] := 'W';
  for i := 0 to n-1 do
    if (vs[i] = 'W') and
       isGCyclic(G,i,vs) then
      Exit(true);
  Exit(false);
end;

// **********************
// *** Program główny ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;
  A : TList;

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // 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
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go
    // na początek listy A[v1]
    p^.next := 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 SLel
{
  SLel * next;
  int v;
};

// Funkcje badające
// cykliczność grafu
//------------------
bool isGCyclic(SLel ** G,
               int v,
               char * vs)
{
  // Wskaźnik elementu listy
  SLel * p;
  int u;

  // Kolorujemy wierzchołek
  // na szaro
  vs[v] = 'G';
  // Sprawdzamy kolejnych sąsiadów
  p = G[v];
  while(p)
  {
    // u <-- numer sąsiada
    u = p->v;
    if(vs[u] == 'G')
      // Sąsiad szary-mamy cykl.
      // Przerywamy
      return true;
    if((vs[u] == 'W') &&
       isGCyclic(G,u,vs))
      // Wywołanie rekurencyjne
      return true;
    p = p->next;
  }
  // Kolorujemy wierzchołek
  // na czarno
  vs[v] = 'B';
  return false;
}

bool isCyclic(int n,
              SLel ** G)
{
  int i;
  char * vs;

  // Tworzymy tablicę odwiedzin
  vs = new char [n];
  for(i = 0; i < n; i++)
    // Tablicę zerujemy
    vs[i] = 'W';
  for(i = 0; i < n; i++)
    if((vs[i] == 'W') &&
       isGCyclic(G,i,vs))
      return true;
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel * p, * r, ** A;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tablice wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    A[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy A[v1]
    p->next = 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 SLel
  next As SLel Ptr
  v As Integer
End Type

' Funkcje badające cykliczność grafu
'-----------------------------------

Const WHITE = 0
Const GRAY = 1
Const BLACK = 2

Function _
  isGCyclic(ByVal G As SLel Ptr Ptr, _
            ByVal v As Integer, _
            ByVal vs As Byte Ptr) _
                          As Integer
  ' Wskaźnik elementu listy
  Dim As SLel ptr p
  Dim As Integer u

  ' Kolorujemy wierzchołek na szaro
  vs[v] = GRAY
  ' Sprawdzamy kolejnych sąsiadów
  p = G[v]
  While p <> 0
    ' u <-- numer sąsiada
    u = p->v
    ' Sąsiad szary-mamy cykl.
    ' Przerywamy
    If vs[u] = GRAY Then Return 1
    If (vs[u] = WHITE) AndAlso _
       (isGCyclic(G,u,vs) = 1) Then
      ' Wywołanie rekurencyjne
      Return 1
    End If
    p = p->next
  Wend
  ' Kolorujemy wierzchołek na czarno
  vs[v] = BLACK
  Return 0
End Function

Function _
  isCyclic(ByVal n As integer, _
           ByVal G As SLel Ptr Ptr) _
                   As Integer
  Dim As Integer i
  Dim As Byte Ptr vs

  ' Tworzymy tablicę odwiedzin
  vs = New Byte [n]
  For i = 0 To n-1
    ' Tablicę zerujemy
    vs[i] = WHITE
  Next
  For i = 0 To n-1
    If (vs[i] = WHITE) AndAlso _
       (isGCyclic(G,i,vs) = 1) Then _
      Return 1
  Next
  Return 0
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę
' list sąsiedztwa
A = new SLel Ptr [n]
' 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
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek
  ' listy A[v1]
  p->next = A[v1]
  A[v1] = p
Next
Close #1
If isCyclic (n, A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
End If
' Usuwamy tablicę
' list sąsiedztwa
For i = 0 To n-1
  p = A [i]
  While p <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] A
End

Python (dodatek)

# Badanie cykliczności
# grafu skierowanego
# Data: 25.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------


# Klasa dla dynamicznej
# tablicy list sąsiedztwa
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Funkcje badające
# cykliczność grafu

WHITE = 0
GRAY = 1
BLACK = 2


def is_g_cyclic(g, v, vs):
    global WHITE, GRAY, BLACK
    # Kolorujemy wierzchołek na szaro
    vs[v] = GRAY
    # Sprawdzamy kolejnych sąsiadów
    p = g[v]
    while p:
        # u <-- numer sąsiada
        u = p.v
        # Sąsiad szary-mamy cykl.
        # Przerywamy
        if vs[u] == GRAY: return True
        if (vs[u] == WHITE) and \
             is_g_cyclic(g,u,vs):
            # Wywołanie rekurencyjne
            return True
        p = p.next
    # Kolorujemy wierzchołek na czarno
    vs[v] = BLACK
    return False


def isCyclic(n, g):
    global WHITE, GRAY, BLACK
    # Tworzymy tablicę odwiedzin
    vs = [WHITE] * n
    for i in range(n):
        if (vs[i] == WHITE) and \
             is_g_cyclic(g,i,vs):
            return True
    return False


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę
# list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek
    # listy a[v1]
    p.next = a[v1]
    a[v1] = p
if isCyclic(n, a):
    print("CYCLIC GRAPH")
else:
    print("ACYCLIC GRAPH")
# Usuwamy tablicę
# list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

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

do podrozdziału do strony

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.

Cykliczność grafu

Problem

Rozwiązanie dla spójnego grafu nieskierowanego

Algorytm sprawdzania cykliczności spójnego grafu nieskierowanego

Funkcja isCyclic(n,graf)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla niespójnego grafu nieskierowanego

Algorytm sprawdzania cykliczności niespójnego grafu nieskierowanego

Funkcja isCCyclic(graf,v,vs)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Funkcja isCyclic(n,graf)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla grafu skierowanego

Algorytm sprawdzania cykliczności grafu skierowanego

Algorytm rekurencyjnej funkcji isGCyclic(graf,v,vs)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm funkcji isCyclic(n,graf)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy