Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Znajdowanie cykli w grafie

SPIS TREŚCI
Podrozdziały

Problem

Dla każdego wierzchołka grafu należy wyznaczyć cykl, który go zawiera.

Rozwiązanie dla grafu nieskierowanego

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 DFSfindCycle ( graf, v, w, S, visited )

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.
visited  –  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.
Zmienne pomocnicze:
u  –  wierzchołek, u  ∈ C.

Lista kroków:

K01: visited [ w  ] ← true oznaczamy bieżący wierzchołek jako odwiedzony
K02: Dla każdego sąsiada u  wierzchołka w :
wykonuj
kroki K03...K07
przeglądamy kolejnych sąsiadów wierzchołka w
K03:     Jeśli u  = S.top( ),
    to następny obieg pętli K02
sąsiad jest wierzchołkiem, z którego przyszliśmy
K04:     S.push ( w  ) wierzchołek w umieszczamy na stosie
K05:     Jeśli u  = v,
    to zakończ
znaleźliśmy cykl, kończymy rekurencję
K06:     Jeśli ( visited [ u  ] = false ) obrazek ( DFSfindCycle ( graf, v, u, S, visited  ) = true ),
    to zakończ z wynikiem true
rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów
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.
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ę.
Zmienne pomocnicze:
i, u  –  wierzchołki, i, u  ∈ C.
visited  –  tablica logiczna.
S  –  stos liczb całkowitych.

Lista kroków:

K01: Utwórz n-elementową tablicę visited  
K02: Utwórz pusty stos S  
K03: Dla i = 0, 1, ..., n - 1:
wykonuj kroki K04...K10
 
K04:     Ustaw wszystkie elementy visited  na false  
K05:     S.push ( -1 ) początek ścieżki
K06:     Jeśli DFSfindCycle ( graf, i, i, S, visited  ) = false,
    to S.pop( )
    i następny obieg pętli K03
szukamy cyklu, wynik będzie na stosie
K07:     Pisz i wypisujemy wierzchołek startowy
K08:     Dopóki S.empty( ) = false,
    wykonuj kroki K09...K10
wypisujemy wierzchołki tworzące cykl
K09:         u  ← S.top( ); S.pop( ) pobieramy wierzchołek
K10:         Jeśli u  > -1,
        to pisz u
wypisujemy go, 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ą DFSfindCycle( ) ).
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
obrazek        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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push ( v : integer );
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

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

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

// Funkcja rekurencyjna wyszukująca cykl
//--------------------------------------
function DFSfindCycle ( var graf : TList; v, w : integer; var S : stack;
                      var visited : array of boolean ) : boolean;
var
  u : integer;
  p : PslistEl;
begin
  visited [ w ] := true;         // Oznaczamy wierzchołek jako odwiedzony
  p := graf [ w ];               // Rozpoczynamy przeglądanie sąsiadów
  while p <> nil do
  begin
    u := p^.v;                   // u - numer wierzchołka będącego sąsiadem
    if u <> S.top then           // Pomijamy wierzchołek, z którego przyszliśmy
    begin
      S.push ( w );              // Na stos wierzchołek bieżący
      if u = v then Exit ( true ); // Cykl znaleziony, kończymy
      if( visited [ u ] = false ) and DFSfindCycle ( graf, v, u, S, visited ) 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;
  visited  : array of boolean;
  S        : stack;
  p, r     : PslistEl;
  A        : TList;

begin
  read ( n, m );           // Czytamy liczbę wierzchołków i krawędzi

  SetLength ( A, n );      // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A [ i ] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read ( v1, v2 );       // Wierzchołek startowy i końcowy krawędzi
    new ( p );             // Tworzymy nowy element
    p^.v := v2;            // Numerujemy go jako v2
    p^.next := A [ v1 ];   // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] := p;
    new ( p );             // Krawędź w drugą stronę, bo graf jest nieskierowany
    p^.v := v1;
    p^.next := A [ v2 ];
    A [ v2 ] := p;
  end;

  writeln;

  SetLength ( visited, n );      // Tworzymy tablicę odwiedzin
  S.init;                        // Tworzymy stos wierzchołków
  for i := 0 to n - 1 do         // Przechodzimy przez kolejne wierzchołki grafu
  begin
    for j := 0 to n - 1 do       // Zerujemy tablicę odwiedzin
      visited [ j ] := false;

    S.push ( -1 );               // Na stos znacznik początku ścieżki

    write ( i );                 // Wypisujemy wierzchołek startowy cyklu

    if DFSfindCycle ( A, i, i, S, visited ) = false then // Szukamy cyklu
    begin
      S.pop;                     // Usuwamy ze stosu początek ścieżki
      writeln ( ' - no cycle' ); // Komunikat
    end
    else
      while S.empty = false do   // Wypisujemy cykl, jeśli istnieje
      begin
        u := S.top; S.pop;       // Pobieramy ze stosu numer wierzchołka
        if u > -1 then write ( ' ', u )// i wypisujemy go
        else           writeln;
      end;
  end;

  // Usuwamy dynamiczne struktury danych

  SetLength ( visited, 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 slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack( );      // konstruktor
    ~stack( );     // destruktor
    bool empty ( void );
    int  top ( void );
    void push ( int v );
    void pop ( void );
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack( )
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack( )
{
  while( S ) pop( );
}

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

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

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

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

// Funkcja rekurencyjna wyszukująca cykl
//--------------------------------------
bool DFSfindCycle ( slistEl ** graf, int v, int w, stack & S, bool * visited )
{
  int u;
  slistEl * p;

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

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

int main( )
{
  int n, m, i, j, u, v1, v2;
  slistEl * p, * r, ** A;
  bool * visited;
  stack S;

  cin >> n >> m;           // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [ n ]; // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for( i = 0; i < n; i++ ) A [ i ] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] = p;
    p = new slistEl;    // Krawędź w drugą stronę, bo graf jest nieskierowany
    p->v = v1;
    p->next = A [ v2 ];
    A [ v2 ] = p;
  }

  cout << endl;

  visited = new bool [ n ];      // Tworzymy tablicę odwiedzin

  for( i = 0; i < n; i++ )       // Przechodzimy przez kolejne wierzchołki grafu
  {
    for( j = 0; j < n; j++ )     // Zerujemy tablicę odwiedzin
      visited [ j ] = false;

    S.push ( -1 );               // Na stos znacznik początku ścieżki

    cout << i;                   // Wypisujemy wierzchołek startowy cyklu

    if( !DFSfindCycle ( A, i, i, S, visited ) ) // Szukamy cyklu
    {
      S.pop( );                  // Usuwamy ze stosu początek ścieżki
      cout << " - no cycle\n";   // Komunikat
    }
    else
      while( !S.empty( ) )       // Wypisujemy cykl, jeśli istnieje
      {
        u = S.top( ); S.pop( );  // Pobieramy ze stosu numer wierzchołka
        if( u > -1 ) cout << " " << u; // i wypisujemy go
        else       cout << endl;
      }
  }

  // Usuwamy dynamiczne struktury danych

  delete [ ] visited;

  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 slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor( )
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function top As Integer
    Declare Sub push ( ByVal v As Integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack( )
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack( )
  While S
    pop( )
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty( ) As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top( ) As Integer
  top = S->v
End Function

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

' Usuwa ze stosu
'---------------
Sub stack.pop( )
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja rekurencyjna wyszukująca cykl
'--------------------------------------
Function DFSfindCycle ( ByVal graf As slistEl Ptr Ptr,_
	                  ByVal v As integer, ByVal w As integer,_
	                  ByRef S As stack,_
	                  ByVal visited As Integer Ptr ) As Integer

  Dim As Integer u
  Dim As slistEl Ptr p

  visited [ w ] = 1            ' Oznaczamy wierzchołek jako odwiedzony
  p = graf [ w ]               ' Rozpoczynamy przeglądanie sąsiadów
  While p
    u = p->v                   ' u - numer wierzchołka będącego sąsiadem
    If u <> S.top( ) Then      ' Pomijamy wierzchołek, z którego przyszliśmy
      S.push ( w )             ' Na stos wierzchołek bieżący
      If u = v Then Return 1   ' Cykl znaleziony, kończymy
      if( visited [ u ] = 0 ) AndAlso ( DFSfindCycle ( graf, v, u, S, visited ) = 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 slistEl Ptr p, r
Dim As slistEl Ptr Ptr A
Dim As Integer Ptr visited
Dim As stack S

Open Cons For Input As #1

Input #1, n, m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [ n ] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1, v1, v2     ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A [ v1 ]   ' Dodajemy go na początek listy A [ v1 ] 
  A [ v1 ] = p
  p = new slistEl      ' Krawędź w drugą stronę, bo graf jest nieskierowany
  p->v = v1
  p->next = A [ v2 ] 
  A [ v2 ] = p
Next

Close #1

Print

visited = New Integer [ n ]    ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1             ' Przechodzimy przez kolejne wierzchołki grafu
  For j = 0 To n - 1           ' Zerujemy tablicę odwiedzin
    visited [ j ] = 0
  Next
  
  S.push ( -1 )                ' Na stos znacznik początku ścieżki

  Print i;                     ' Wypisujemy wierzchołek startowy cyklu

  If DFSfindCycle ( A, i, i, S, visited ) = 0 Then ' Szukamy cyklu
    S.pop( )                   ' Usuwamy ze stosu początek ścieżki
    Print " - no cycle"        ' Komunikat
  Else
    While S.empty( ) = 0       ' Wypisujemy cykl, jeśli istnieje
      u = S.top( ): S.pop( )   ' Pobieramy ze stosu numer wierzchołka
      If u > -1 Then
        Print u;               ' i wypisujemy go
      Else
        Print
      End If
    Wend
  End If
Next

' Usuwamy dynamiczne struktury danych

Delete [ ] visited

For i = 0 To n - 1
  p = A [ i ] 
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [ ] A

End
Wynik:
9 10
0 1 0 3
1 8
2 4 2 5
3 7 3 8
4 6
5 6 5 7

0 1 8 3 0
1 0 3 8 1
2 4 6 5 2
3 0 1 8 3
4 2 5 6 4
5 2 4 6 5
6 4 2 5 6
7 - no cycle
8 1 0 3 8
Na początek:  podrozdziału   strony 

Rozwiązanie dla grafu skierowanego

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 DFSfindCycle ( graf, v, w, S, visited )

Wejście:

graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v  –  wierzchołek startowy.
w  –  wierzchołek bieżący.
S  –  stos liczb całkowitych będących numerami wierzchołków.
visited  –  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.
Zmienne pomocnicze:
u  –  wierzchołek, u  ∈ C.

Lista kroków:

K01: visited [ 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 :
wykonuj
kroki K04...K05
przeglądamy kolejnych sąsiadów wierzchołka w
K04:     Jeśli u  = v,
    to zakończ z wynikiem true
znaleźliśmy cykl, kończymy rekurencję
K05:     Jeśli ( visited [ u  ] = false ) obrazek ( DFSfindCycle ( graf, v, u, S, visited  ) = 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.
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ę.
Zmienne pomocnicze:
i, u  –  wierzchołki, i, u  ∈ C.
visited  –  tablica logiczna.
S  –  stos liczb całkowitych.

Lista kroków:

K01: Utwórz n-elementową tablicę visited  
K02: Utwórz pusty stos S  
K03: Dla i = 0, 1, ..., n - 1:
wykonuj kroki K04...K09
 
K04:     Ustaw wszystkie elementy visited  na false  
K05:     Jeśli DFSfindCycle ( graf, i, i, S, visited  ) = false,
    to następny obieg pętli K03
szukamy cyklu, wynik będzie na stosie
K06:     Pisz i wypisujemy wierzchołek startowy
K07:     Dopóki S.empty( ) = false,
    wykonuj kroki K08...K09
wypisujemy wierzchołki 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ą DFSfindCycle( ) ). Przy wyświetlaniu cyklu odwracamy kolejność wierzchołków.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
obrazek   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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push ( v : integer );
    procedure  pop;
end;

// Konstruktor
//------------
constructor stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------

destructor stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function stack.empty : boolean;
begin
  if S = nil then empty := true else empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function stack.top : integer;
begin
  top := S^.v;
end;

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

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

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

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

var
  n, m, i, j, v1, v2 : integer;
  visited       : array of boolean;
  S, T          : stack;
  p, r          : PslistEl;
  A             : TList;

begin
  read ( n, m );         // Czytamy liczbę wierzchołków i krawędzi

  SetLength ( A, n );    // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for i := 0 to n - 1 do A [ i ] := nil;

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 do
  begin
    read ( v1, v2 );     // Wierzchołek startowy i końcowy krawędzi
    new ( p );           // Tworzymy nowy element
    p^.v := v2;          // Numerujemy go jako v2
    p^.next := A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] := p;
  end;

  writeln;

  SetLength ( visited, n );      // Tworzymy tablicę odwiedzin
  S.init;                        // Tworzymy stosy wierzchołków
  T.init;
  for i := 0 to n - 1 do         // Przechodzimy przez kolejne wierzchołki grafu
  begin
    for j := 0 to n - 1 do       // Zerujemy tablicę odwiedzin
      visited [ j ] := false;

    if DFSfindCycle ( A, i, i, S, visited ) = false then // Szukamy cyklu
      writeln ( i, ' - no cycle' )
    else
    begin
      T.push ( i );
      while S.empty = false do   // Przerzucamy stos S do stosu T
      begin
        T.push ( S.top ); S.pop;
      end;

      while T.empty = false do   // Wyświetlamy ścieżkę
      begin
        write ( T.top( ), ' ' ); T.pop;
      end;
      writeln;
    end;
  end;

  // Usuwamy dynamiczne struktury danych

  SetLength ( visited, 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 slistEl
{
  slistEl * next;
  int v;
};

class stack
{
  private:
    slistEl * S;   // lista przechowująca stos

  public:
    stack( );       // konstruktor
    ~stack( );      // destruktor
    bool empty ( void );
    int  top ( void );
    void push ( int v );
    void pop ( void );
};

//---------------------
// Metody obiektu stack
//---------------------

// Konstruktor
//------------
stack::stack( )
{
  S = NULL;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
stack::~stack( )
{
  while( S ) pop( );
}

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

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

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

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

// Funkcja rekurencyjna wyszukująca cykl
//--------------------------------------
bool DFSfindCycle ( slistEl ** graf, int v, int w, stack & S, bool * visited )
{
  int u;
  slistEl * p;

  visited [ w ] = true;       // Oznaczamy wierzchołek jako odwiedzony
  S.push ( w );               // Na stos wierzchołek bieżący
  p = graf [ w ];             // Rozpoczynamy przeglądanie sąsiadów
  while( p )
  {
    u = p->v;                 // u - numer wierzchołka będącego sąsiadem

    if( u == v ) return true; // Cykl znaleziony, kończymy

    if( !visited [ u ] && DFSfindCycle ( graf, v, u, S, visited ) ) return true;

    p = p->next;
  }
  S.pop( );             // Usuwamy bieżący wierzchołek ze stosu
  return false;
}

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

int main( )
{
  int n, m, i, j, v1, v2;
  slistEl * p, * r, ** A;
  bool * visited;
  stack S, T;

  cin >> n >> m;        // Czytamy liczbę wierzchołków i krawędzi

  A = new slistEl * [ n ]; // Tworzymy tablicę list sąsiedztwa

  // Tablice wypełniamy pustymi listami

  for( i = 0; i < n; i++ ) A [ i ] = NULL;

  // Odczytujemy kolejne definicje krawędzi

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;    // Wierzchołek startowy i końcowy krawędzi
    p = new slistEl;    // Tworzymy nowy element
    p->v = v2;          // Numerujemy go jako v2
    p->next = A [ v1 ]; // Dodajemy go na początek listy A [ v1 ] 
    A [ v1 ] = p;
  }

  cout << endl;

  visited = new bool [ n ];  // Tworzymy tablicę odwiedzin

  for( i = 0; i < n; i++ )   // Przechodzimy przez kolejne wierzchołki grafu
  {
    for( j = 0; j < n; j++ ) // Zerujemy tablicę odwiedzin
      visited [ j ] = false;

    if( !DFSfindCycle ( A, i, i, S, visited ) ) // Szukamy cyklu
      cout << i << " - no cycle\n";  // Komunikat
    else
    {
      T.push ( i );
      while( !S.empty( ) )  // Przerzucamy stos S do stosu T
      {
        T.push ( S.top( ) ); S.pop( );
      }

      while( !T.empty( ) )  // Wyświetlamy ścieżkę
      {
        cout << T.top( ) << " "; T.pop( );
      }
      cout << endl;
    }
  }

  // Usuwamy dynamiczne struktury danych

  delete [ ] visited;

  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 slistEl
  next As slistEl Ptr
  v As Integer
End Type

Type stack
  Private:
    S As slistEl Ptr  ' lista zawierająca stos
  Public:
    Declare Constructor( )
    Declare Destructor( )
    Declare Function empty( ) As Integer
    Declare Function top As Integer
    Declare Sub push ( ByVal v As Integer )
    Declare Sub pop( )
End Type

'---------------------
' Metody obiektu stack
'---------------------

' Konstruktor
'------------
Constructor stack( )
  S = 0
End Constructor

' Destruktor
'-----------
Destructor stack( )
  While S
    pop( )
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function stack.empty( ) As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu.
'------------------------------
Function stack.top( ) As Integer
  top = S->v
End Function

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

' Usuwa ze stosu
'---------------
Sub stack.pop( )
  Dim e As slistEl Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja rekurencyjna wyszukująca cykl
'--------------------------------------
Function DFSfindCycle ( ByVal graf As slistEl Ptr Ptr, _
	                  ByVal v As integer, ByVal w As integer, _
	                  ByRef S As stack, _
	                  ByVal visited As Integer Ptr ) As Integer

  Dim As Integer u
  Dim As slistEl Ptr p

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

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

Dim As Integer n, m, i, j, v1, v2
Dim As slistEl Ptr p, r
Dim As slistEl Ptr Ptr A
Dim As Integer Ptr visited
Dim As stack S, T

Open Cons For Input As #1

Input #1, n, m            ' Czytamy liczbę wierzchołków i krawędzi

A = new slistEl Ptr [ n ] ' Tworzymy tablicę list sąsiedztwa

' Tablicę wypełniamy pustymi listami

For i = 0 To n - 1
  A [ i ] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  Input #1, v1, v2     ' Wierzchołek startowy i końcowy krawędzi
  p = new slistEl      ' Tworzymy nowy element
  p->v = v2            ' Numerujemy go jako v2
  p->next = A [ v1 ]   ' Dodajemy go na początek listy A [ v1 ] 
  A [ v1 ] = p
Next

Close #1

Print

visited = New Integer [ n ] ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1          ' Przechodzimy przez kolejne wierzchołki grafu
  For j = 0 To n - 1        ' Zerujemy tablicę odwiedzin
    visited [ j ] = 0
  Next
  
  If DFSfindCycle ( A, i, i, S, visited ) = 0 Then ' Szukamy cyklu
    Print i;" - no cycle"   ' Komunikat
  Else
    T.push ( i )
    While S.empty( ) = 0    ' Przerzucamy stos S do stosu T
      T.push ( S.top( ) ): S.pop( )
    Wend

    While T.empty( ) = 0    ' Wyświetlamy ścieżkę
      Print T.top( );
      T.pop( )
    Wend
    Print
  End If
Next

' Usuwamy dynamiczne struktury danych

Delete [ ] visited

For i = 0 To n - 1
  p = A [ i ] 
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [ ] A

End
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.