Algorytmy i Struktury Danych - Znajdowanie cykli w grafie

Problem rozwiązujemy za pomocą przejścia DFS. Dany wierzchołek będzie częścią cyklu, jeśli DFS wróci do któregoś z sąsiadów wierzchołka, a nie będzie to sąsiad, od którego DFS rozpoczęło przejście grafu. W trakcie przechodzenia grafu algorytm DFS zapamiętuje na osobnym stosie kolejno odwiedzane wierzchołki. Gdy wykryje cykl, stos ten będzie zawierał wierzchołki tworzące ten cykl. Wtedy wystarczy pobrać ze stosu wszystkie wierzchołki i przerwać dalsze przeglądanie grafu.

Algorytm znajdowania cykli w grafie nieskierowanym

Rekurencyjna funkcja FCycle(graf,v,w,S,vs)

Wejście:

graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : wierzchołek startowy; v ∈ C.
w : wierzchołek bieżący; w ∈ C.
S : stos liczb całkowitych będących numerami wierzchołków.
vs : tablica logiczna wierzchołków odwiedzonych.

Wyjście:

true – znaleziono cykl, false – brak cyklu.
S – zawiera ciąg wierzchołków, które tworzą cykl. Jeśli stos S jest pusty, to wierzchołek v nie jest częścią żadnego cyklu.

Elementy pomocnicze:

u : wierzchołek; u ∈ C.

Lista kroków:

K01: vs[w] ← true ; oznaczamy bieżący wierzchołek jako odwiedzony
K02: ; przeglądamy kolejnych sąsiadów wierzchołka w
     Dla każdego sąsiada u wierzchołka w:
     wykonuj kroki K03…K07
K03:   ; sąsiad jest wierzchołkiem, z którego przyszliśmy
       Jeśli u = S.top(),
       to następny obieg pętli K02
K04:   S.push(w) ; wierzchołek w umieszczamy na stosie
K05:   Jeśli u = v, ; znaleźliśmy cykl, kończymy rekurencję
       to zakończ z wynikiem true
K06:   ; rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów
       Jeśli (vs[u] = false)  (FCycle(graf,v,u,S,vs) = true),
       to zakończ z wynikiem true
K07:   S.pop() ; usuwamy ze stosu wierzchołek bieżący
K08: Zakończ z wynikiem false

Algorytm podstawowy

Wejście:

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

Wyjście:

Dla każdego wierzchołka grafu znajduje cykl, który go zawiera. Jeśli wierzchołek nie jest częścią cyklu, otrzymujemy pustą ścieżkę.

Elementy pomocnicze:

i,u : wierzchołki; i,u ∈ C.
vs : tablica logiczna.
S : stos liczb całkowitych.

Lista kroków:

K01: Utwórz n elementową tablicę vs
K02: Utwórz pusty stos S
K03: Dla i = 0, 1, …, n-1:
     wykonuj kroki K04…K10
K04:   Ustaw wszystkie elementy vs na false
K05:   S.push(-1) ; początek ścieżki
K06:   ; szukamy cyklu, wynik będzie na stosie
       Jeśli FCycle(graf,i,i,S,vs) = false,
       to S.pop()
       i następny obieg pętli K03
K07:   Pisz i ; wypisujemy wierzchołek startowy
K08:   ; wypisujemy wierzchołki tworzące cykl
       Dopóki S.empty() = false, 
       wykonuj kroki K09…K10
K09:   u ← S.top(); S.pop() ; pobieramy wierzchołek
K10:   Jeśli u > -1, ; wypisujemy go,
       to pisz u ; jeśli nie jest początkiem ścieżki
K11: Zakończ

Uwaga: algorytm wypisuje cykle w odwrotnej kolejności niż były przechodzone przez DFS. Jeśli chcesz mieć normalną kolejność, to dane odczytane ze stosu S należy wypisać w kolejności odwrotnej (można tego prosto dokonać za pomocą dodatkowego stosu).

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ę grafu nieskierowanego i dla każdego wierzchołka wypisuje znaleziony cykl. Jeśli cyklu nie ma, to zostaje wyświetlona odpowiednia informacja (wykorzystujemy informację o znalezieniu cyklu, która jest zwracana przez funkcję rekurencyjną FCycle()).

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

9 10
0 1
0 3
1 8
2 4
2 5
3 7
3 8
4 6
5 6
5 7

Pascal

// Wyszukiwanie cykli
// w grafie nieskierowanym
// Data: 22.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program fndcycles;

// 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 := -MAXINT
  else
    top := S^.v;
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 rekurencyjna
// wyszukująca cykl
//---------------------
function FCycle(var graf : TList;
   v, w : integer;
  var S : Stack;
 var vs : array of boolean)
        : boolean;
var
  u : integer;
  p : PSLel;

begin
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[w] := true;
  // Rozpoczynamy
  // przeglądanie sąsiadów
  p := graf[w];
  while p <> nil do
  begin
    // u - numer wierzchołka
    // będącego sąsiadem
    u := p^.v;
    // Pomijamy wierzchołek,
    // z którego przyszliśmy
    if u <> S.top then
    begin
      // Na stos wierzchołek bieżący
      S.push(w);
      // Cykl znaleziony, kończymy
      if u = v then Exit(true);
      if (vs[u] = false) and
         FCycle(graf,v,u,S,vs) then
        Exit(true);
      S.pop;
    end;
    p := p^.next;
  end;
  Exit(false);
end;

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

var
  n, m, i, j, u, v1, v2 : integer;
  vs : array of boolean;
  S  : Stack;
  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;
  writeln;
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tworzymy stos wierzchołków
  S.init;
  // Przechodzimy przez
  // kolejne wierzchołki grafu
  for i := 0 to n-1 do
  begin
    // Zerujemy tablicę odwiedzin
    for j := 0 to n-1 do
      vs[j] := false;
    // Na stos znacznik
    // początku ścieżki
    S.push(-1);
    // Wypisujemy wierzchołek
    // startowy cyklu
    write(i);
    // Szukamy cyklu
    if FCycle(A,i,i,S,vs) = false then
    begin
      // Usuwamy ze stosu
      // początek ścieżki
      S.pop;
      // Komunikat
      writeln('-no cycle');
    end
    else
      // Wypisujemy cykl,
      // jeśli istnieje
      while S.empty = false do
      begin
        // Pobieramy ze stosu
        // numer wierzchołka
        u := S.top; S.pop;
        // i wypisujemy go
        if u > -1 then
          write(' ', u)
        else
          writeln;
      end;
  end;
  // Usuwamy dynamiczne
  // struktury danych
  SetLength(vs, 0);
  S.destroy;
  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++

// Wyszukiwanie cykli
// w grafie nieskierowanym
// Data: 22.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 rekurencyjna
// wyszukująca cykl
//---------------------
bool FCycle(SLel ** graf,
            int v,
            int w,
            Stack & S,
            bool * vs)
{
  int u;
  SLel * p;

  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[w] = true;
  // Rozpoczynamy
  // przeglądanie sąsiadów
  p = graf[w];
  while(p)
  {
    // u - numer wierzchołka
    // będącego sąsiadem
    u = p->v;
    // Pomijamy wierzchołek,
    // z którego przyszliśmy
    if(u != S.top())
    {
      // Na stos wierzchołek bieżący
      S.push(w);
      // Cykl znaleziony, kończymy
      if(u == v) return true;
      if(!vs[u] &&
         FCycle(graf,v,u,S,vs))
        return true;
      S.pop();
    }
    p = p->next;
  }
  return false;
}

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

int main()
{
  int n, m, i, j, u, v1, v2;
  SLel * p, * r, ** A;
  bool * vs;
  Stack S;

  // 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;
  }
  cout << endl;
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Przechodzimy przez
  // kolejne wierzchołki grafu
  for(i = 0; i < n; i++)
  {
    // Zerujemy tablicę odwiedzin
    for(j = 0; j < n; j++)
      vs[j] = false;
    // Na stos znacznik
    // początku ścieżki
    S.push(-1);
    // Wypisujemy wierzchołek
    // startowy cyklu
    cout << i;
    // Szukamy cyklu
    if(!FCycle(A,i,i,S,vs))
    {
      // Usuwamy ze stosu
      // początek ścieżki
      S.pop();
      // Komunikat
      cout << "-no cycle\n";
    }
    else
      // Wypisujemy cykl,
      // jeśli istnieje
      while(!S.empty())
      {
        // Pobieramy ze stosu
        // numer wierzchołka
        u = S.top(); S.pop();
        if(u > -1)
          // i wypisujemy go
          cout << " " << u;
        else
          cout << endl;
      }
  }
  // Usuwamy dynamiczne
  // struktury danych
  delete [] vs;
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  return 0;
}

Basic

' Wyszukiwanie cykli
' w grafie nieskierowanym
' Data: 22.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 <> 0
    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 Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja rekurencyjna
' wyszukująca cykl
'---------------------
Function FCycle _
  (ByVal graf As SLel Ptr Ptr, _
   ByVal v As integer, _
   ByVal w As integer, _
   ByRef S As Stack, _
   ByVal vs As Integer Ptr) _
            As Integer
  Dim As Integer u
  Dim As SLel Ptr p

  ' Oznaczamy wierzchołek
  ' jako odwiedzony
  vs[w] = 1
  ' Rozpoczynamy
  ' przeglądanie sąsiadów
  p = graf[w]
  While p
    ' u - numer wierzchołka
    '     będącego sąsiadem
    u = p->v
    ' Pomijamy wierzchołek,
    ' z którego przyszliśmy
    If u <> S.top Then
      ' Na stos wierzchołek bieżący
      S.push(w)
      ' Cykl znaleziony, kończymy
      If u = v Then Return 1
      if (vs[u] = 0) AndAlso _
         (FCycle(graf,v,u,S,vs) = 1) _
      Then Return 1
      S.pop
    End If
    p = p->next
  Wend
  Return 0
End Function

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

Dim As Integer n, m, i, j, u, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A
Dim As Integer Ptr vs
Dim As Stack S

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
Print
' Tworzymy tablicę odwiedzin
vs = New Integer [n]
' Przechodzimy przez
' kolejne wierzchołki grafu
For i = 0 To n-1
  ' Zerujemy tablicę odwiedzin
  For j = 0 To n-1
    vs[j] = 0
  Next
  ' Na stos znacznik
  ' początku ścieżki
  S.push(-1)
  ' Wypisujemy wierzchołek
  ' startowy cyklu
  Print i;
  ' Szukamy cyklu
  If FCycle(A,i,i,S,vs) = 0 Then
    ' Usuwamy ze stosu
    ' początek ścieżki
    S.pop
    ' Komunikat
    Print "-no cycle"
  Else
    ' Wypisujemy cykl,
    ' jeśli istnieje
    While S.empty = 0
      ' Pobieramy ze stosu
      ' numer wierzchołka
      u = S.top: S.pop
      If u > -1 Then
        ' i wypisujemy go
        Print u;
      Else
        Print
      End If
    Wend
  End If
Next
' Usuwamy dynamiczne
' struktury danych
Delete [] vs
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)

# Wyszukiwanie cykli
# w grafie nieskierowanym
# Data: 28.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 s:
            return self.s.v
        else:
            return -MAXINT


    # 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 rekurencyjna
# wyszukująca cykl
def f_cycle(graf, v, w, s, vs):
    # Oznaczamy wierzchołek
    # jako odwiedzony
    vs[w] = True
    # Rozpoczynamy
    # przeglądanie sąsiadów
    p = graf[w]
    while p:
        # u - numer wierzchołka
        #     będącego sąsiadem
        u = p.v
        # Pomijamy wierzchołek,
        # z którego przyszliśmy
        if u != s.top():
            # Na stos
            # wierzchołek bieżący
            s.push(w)
            # Cykl znaleziony,
            # kończymy
            if u == v: return True
            if (not vs[u]) and \
               f_cycle(graf,v,u,s,vs):
                return True
            s.pop()
        p = p.next
    return False


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

s = Stack()
# 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
print()
# Przechodzimy przez
# kolejne wierzchołki grafu
for i in range(n):
    # Tworzymy tablicę odwiedzin
    vs = [False] * n
    # Na stos znacznik
    # początku ścieżki
    s.push(-1)
    # Wypisujemy wierzchołek
    # startowy cyklu
    print(i, end=" ")
    # Szukamy cyklu
    if not f_cycle(a,i,i,s,vs):
        # Usuwamy ze stosu
        # początek ścieżki
        s.pop()
        # Komunikat
        print("- no cycle")
    else:
        # Wypisujemy cykl,
        # jeśli istnieje
        while not s.empty():
            # Pobieramy ze stosu
            # numer wierzchołka
            u = s.top()
            s.pop()
            if u > -1:
                # i wypisujemy go
                print(u, end=" ")
            else:
                print()
# Usuwamy dynamiczne
# struktury danych
del vs
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

Wynik:

do podrozdziału do strony

Problem rozwiązujemy za pomocą przejścia DFS. Dany wierzchołek będzie częścią cyklu, jeśli DFS znajdzie wierzchołek w grafie, od którego prowadzi krawędź do wierzchołka startowego. Zadanie to jest nawet prostsze od wyszukiwania cyklu w grafie nieskierowanym, ponieważ z listy sąsiadów nie musimy eliminować wierzchołków, z których przyszliśmy.

Algorytm znajdowania cykli w grafie skierowanym

Rekurencyjna funkcja FCycle(graf,v,w,S,vs)

Wejście:

Wyjście:

true – znaleziono cykl, false – brak cyklu.
S – zawiera ciąg wierzchołków, które tworzą cykl. Jeśli stos S jest pusty, to wierzchołek v nie jest częścią żadnego cyklu.

Elementy pomocnicze:

u : wierzchołek; u ∈ C.

Lista kroków:

K01: vs[w] ← true ; oznaczamy bieżący wierzchołek jako odwiedzony
K02: S.push(w) ; na stosie umieszczamy bieżący wierzchołek
K03: Dla każdego sąsiada u wierzchołka w: ; przeglądamy kolejnych
     wykonuj kroki K04…K05 ; sąsiadów wierzchołka w
K04:   Jeśli u = v, ; znaleźliśmy cykl, kończymy rekurencję
       to zakończ z wynikiem true
K05:   Jeśli (vs[u] = false)  (FCycle(graf,v,u,S,vs) = true), 
       to zakończ z wynikiem true ; rekurencyjnie odwiedzamy
       ; nieodwiedzonych sąsiadów
K06: S.pop() ; usuwamy ze stosu wierzchołek bieżący
K07: Zakończ z wynikiem false

Algorytm podstawowy

Wejście:

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

Wyjście:

Dla każdego wierzchołka grafu znajduje cykl, który go zawiera. Jeśli wierzchołek nie jest częścią cyklu, otrzymujemy pustą ścieżkę.

Elementy pomocnicze:

i,u : wierzchołki, i,u ∈ C.
vs : tablica logiczna.
S : stos liczb całkowitych.

Lista kroków:

K01: Utwórz n elementową tablicę vs
K02: Utwórz pusty stos S
K03: Dla i = 0, 1, …, n-1:
     wykonuj kroki K04…K09
K04:   Ustaw wszystkie elementy vs na false
K05:   Jeśli FCycle(graf,i,i,S,vs) = false, ; szukamy cyklu,
       to następny obieg pętli K03 ; wynik będzie na stosie
K06:   Pisz i ; wypisujemy wierzchołek startowy
K07:   Dopóki S.empty() = false, ; wypisujemy wierzchołki
       wykonuj kroki K08…K09 ; tworzące cykl
K08:     Pisz S.top() ; wypisujemy wierzchołek
K09:     S.pop() ; usuwamy go ze stosu
K10: Zakończ

Uwaga: algorytm wypisuje cykle w odwrotnej kolejności. Jeśli chcesz mieć kolejność wzdłuż krawędzi, to dane odczytane ze stosu S należy wypisać wspak (można tego prosto dokonać za pomocą dodatkowego stosu-patrz przykładowe programy).

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ę grafu skierowanego i dla każdego wierzchołka wypisuje znaleziony cykl. Jeśli cyklu nie ma, to zostaje wyświetlona odpowiednia informacja (wykorzystujemy informację o znalezieniu cyklu, która jest zwracana przez funkcję rekurencyjną FCycle()). Przy wyświetlaniu cyklu odwracamy kolejność wierzchołków.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

9 15
0 1
1 4
2 5
3 0
3 1
4 2
5 1
5 8
6 3
6 4
7 4
7 5
7 6
7 8
8 3

Pascal

// Wyszukiwanie cykli
// w grafie skierowanym
// Data: 19.12.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program fndcycles;

// 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 rekurencyjna
// wyszukująca cykl
//---------------------
function FCycle(var graf : TList;
                    v, w : integer;
                   var S : Stack;
                  var vs : array of boolean)
                         : boolean;
var
  u : integer;
  p : PSLel;
begin
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[w] := true;
  // Na stos
  // wierzchołek bieżący
  S.push(w);
  // Rozpoczynamy
  // przeglądanie sąsiadów
  p := graf[w];
  while p <> nil do
  begin
    // u - numer wierzchołka
    //     będącego sąsiadem
    u := p^.v;
    // Cykl znaleziony, kończymy
    if u = v then Exit(true);
    if (vs[u] = false) and
        FCycle(graf,v,u,S,vs)
    then Exit(true);
    p := p^.next;
  end;
  // Usuwamy bieżący
  // wierzchołek ze stosu
  S.pop;
  Exit(false);
end;

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

var
  n, m, i, j, v1, v2 : integer;
  vs : array of boolean;
  S, T : Stack;
  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;
  writeln;
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tworzymy stosy wierzchołków
  S.init;
  T.init;
  // Przechodzimy przez
  // kolejne wierzchołki grafu
  for i := 0 to n-1 do
  begin
    // Zerujemy tablicę odwiedzin
    for j := 0 to n-1 do
      vs[j] := false;
    // Szukamy cyklu
    if FCycle(A,i,i,S,vs) = false then
      writeln(i, '-no cycle')
    else
    begin
      T.push(i);
      // Przerzucamy
      // stos S do stosu T
      while S.empty = false do
      begin
        T.push(S.top);
        S.pop;
      end;
      // Wyświetlamy ścieżkę
      while T.empty = false do
      begin
        write(T.top(), ' ');
        T.pop;
      end;
      writeln;
    end;
  end;
  // Usuwamy dynamiczne
  // struktury danych
  SetLength(vs, 0);
  S.destroy;
  T.destroy;
  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++

// Wyszukiwanie cykli
// w grafie skierowanym
// Data: 19.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 rekurencyjna wyszukująca cykl
//--------------------------------------
bool FCycle(SLel ** graf,
            int v,
            int w,
            Stack & S,
            bool * vs)
{
  int u;
  SLel * p;

  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[w] = true;
  // Na stos
  // wierzchołek bieżący
  S.push(w);
  // Rozpoczynamy
  // przeglądanie sąsiadów
  p = graf[w];
  while(p)
  {
    // u - numer wierzchołka
    //     będącego sąsiadem
    u = p->v;
    // Cykl znaleziony, kończymy
    if(u == v) return true;
    if(!vs[u] &&
       FCycle(graf,v,u,S,vs))
      return true;
    p = p->next;
  }
  // Usuwamy bieżący
  // wierzchołek ze stosu
  S.pop();
  return false;
}

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

int main()
{
  int n, m, i, j, v1, v2;
  SLel * p, * r, ** A;
  bool * vs;
  Stack S, T;

  // 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;
  }
  cout << endl;
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Przechodzimy przez kolejne
  // wierzchołki grafu
  for(i = 0; i < n; i++)
  {
    // Zerujemy tablicę odwiedzin
    for(j = 0; j < n; j++)
      vs[j] = false;
    // Szukamy cyklu
    if(!FCycle(A,i,i,S,vs))
      // Komunikat
      cout << i << "-no cycle\n";
    else
    {
      T.push(i);
      // Przerzucamy
      // stos S do stosu T
      while(!S.empty())
      {
        T.push(S.top());
        S.pop();
      }
      // Wyświetlamy ścieżkę
      while(!T.empty())
      {
        cout << T.top() << " ";
        T.pop();
      }
      cout << endl;
    }
  }
  // Usuwamy dynamiczne
  // struktury danych
  delete [] vs;
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  return 0;
}

Basic

' Wyszukiwanie cykli
' w grafie skierowanym
' Data: 22.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 <> 0
    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 Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja rekurencyjna
' wyszukująca cykl
'---------------------
Function FCycle _
(ByVal graf As SLel Ptr Ptr, _
 ByVal v As integer, _
 ByVal w As integer, _
 ByRef S As Stack, _
 ByVal vs As Integer Ptr) _
          As Integer

  Dim As Integer u
  Dim As SLel Ptr p

  ' Oznaczamy wierzchołek
  ' jako odwiedzony
  vs[w] = 1
  ' Na stos wierzchołek bieżący
  S.push(w)
  ' Rozpoczynamy przeglądanie sąsiadów
  p = graf[w]
  While p
    ' u - numer wierzchołka
    '     będącego sąsiadem
    u = p->v
    ' Cykl znaleziony, kończymy
    If u = v Then Return 1
    If (vs[u] = 0) AndAlso _
       (FCycle(graf,v,u,S,vs) = 1) _
    Then Return 1
    p = p->next
  Wend
  ' Usuwamy bieżący
  ' wierzchołek ze stosu
  S.pop
  Return 0
End Function

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

Dim As Integer n, m, i, j, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A
Dim As Integer Ptr vs
Dim As Stack S, T

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
Print
' Tworzymy tablicę odwiedzin
vs = New Integer [n]
' Przechodzimy przez
' kolejne wierzchołki grafu
For i = 0 To n-1
  ' Zerujemy tablicę odwiedzin
  For j = 0 To n-1
    vs[j] = 0
  Next
  ' Szukamy cyklu
  If FCycle(A,i,i,S,vs) = 0 Then
    ' Komunikat
    Print i;"-no cycle"
  Else
    T.push(i)
    ' Przerzucamy stos S do stosu T
    While S.empty = 0
      T.push(S.top)
      S.pop
    Wend
    ' Wyświetlamy ścieżkę
    While T.empty = 0
      Print T.top;
      T.pop
    Wend
    Print
  End If
Next
' Usuwamy dynamiczne
' struktury danych
Delete [] vs
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)

# Wyszukiwanie cykli
# w grafie skierowanym
# Data: 29.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 rekurencyjna
# wyszukująca cykl
def f_cycle(graf, v, w, s, vs):
    # Oznaczamy wierzchołek
    # jako odwiedzony
    vs[w] = True
    # Na stos wierzchołek bieżący
    s.push(w)
    # Rozpoczynamy przeglądanie sąsiadów
    p = graf[w]
    while p:
        # u - numer wierzchołka
        #     będącego sąsiadem
        u = p.v
        # Cykl znaleziony, kończymy
        if u == v: return True
        if (not vs[u]) and \
            f_cycle(graf,v,u,s,vs):
            return True
        p = p.next
    # Usuwamy bieżący
    # wierzchołek ze stosu
    s.pop()
    return False


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

s = Stack()
t = Stack()
# 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
print()
# Przechodzimy przez
# kolejne wierzchołki grafu
for i in range(n):
    # Zerujemy tablicę odwiedzin
    vs = [False] * n
    # Szukamy cyklu
    if not f_cycle(a,i,i,s,vs):
        # Komunikat
        print(i,"-no cycle")
    else:
        t.push(i)
        # Przerzucamy stos S do stosu T
        while not s.empty():
            t.push(s.top())
            s.pop()
        # Wyświetlamy ścieżkę
        while not t.empty():
            print(t.top(), end=" ")
            t.pop()
        print()
# Usuwamy dynamiczne
# struktury danych
del vs
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

Wynik:

9 15
0 1
1 4
2 5
3 0
3 1
4 2
5 1
5 8
6 3
6 4
7 4
7 5
7 6
7 8
8 3

0 1 4 2 5 8 3 0
1 4 2 5 8 3 1
2 5 8 3 1 4 2
3 1 4 2 5 8 3
4 2 5 8 3 1 4
5 8 3 1 4 2 5
6-no cycle
7-no cycle
8 3 1 4 2 5 8

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.

Znajdowanie cykli w grafie

Problem

Rozwiązanie dla grafu nieskierowanego

Algorytm znajdowania cykli w grafie nieskierowanym

Rekurencyjna funkcja FCycle(graf,v,w,S,vs)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm podstawowy

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie dla grafu skierowanego

Algorytm znajdowania cykli w grafie skierowanym

Rekurencyjna funkcja FCycle(graf,v,w,S,vs)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm podstawowy

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy