Cykliczność grafu


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie dla spójnego grafu nieskierowanego
Rozwiązanie dla niespójnego grafu nieskierowanego
Rozwiązanie dla grafu skierowanego

Problem 1

Zbadać, czy dany graf jest cykliczny

 

 

Rozwiązanie dla spójnego grafu nieskierowanego

Cykl jest ścieżką, która rozpoczyna się i kończy w tym samym wierzchołku. Aby stwierdzić, czy graf zawiera jakiś cykl, przechodzimy go algorytmem DFS. Jeśli w trakcie przechodzenia natrafimy na wierzchołek już odwiedzony, a nie jest to wierzchołek, z którego przyszliśmy, to graf jest cykliczny. W przeciwnym razie graf jest acykliczny.

Prześledźmy na prostym przykładzie badanie cykliczności grafu.

 

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
visited    n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Ustaw wszystkie elementy tablicy visited na false  
K03: Utwórz pusty stos S  
K04: S.push(0) ; na stosie umieszczamy numer wierzchołka startowego
K05: S.push(-1) ; oraz numer wierzchołka, z którego przyszliśmy, -1 = żaden
K06: visited[0] ← true ; wierzchołek zaznaczamy jako odwiedzony
K07: Dopóki S.empty() = false, wykonuj K08...K12 ; w pętli przechodzimy graf algorytmem DFS
K08:     wS.top(); S.pop() ; w – wierzchołek, z którego przyszliśmy
K09:     vS.top(); S.pop() ; v – wierzchołek bieżący
K10:     Dla każdego sąsiada z wierzchołka v wykonuj K11...K12  
K11:         Jeśli visited[z] = false, to
            S.push(z)
            S.push(v)
            visited[z] ← true
            Następny obieg pętli K10
; jeśli sąsiad nie jest odwiedzony,
; to umieszczamy go na stosie
; wraz z numerem bieżącego wierzchołka
K12:         Jeśli zw, to zakończ z wynikiem true ; trafiliśmy na odwiedzony wierzchołek, z którego nie przyszliśmy
; graf jest cykliczny
K13: Zakończ z wynikiem false ; nigdzie nie natrafiliśmy na odwiedzony wcześniej wierzchołek
; graf nie jest cykliczny

 

Program

Ważne:

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

Przykładowe dane dla programu:

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

 

Lazarus
// Badanie cykliczności spójnego grafu nieskierowanego
// Data: 10.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------------------

program testcyclic;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if isCyclic(n,A) then writeln('CYCLIC GRAPH')
  else                  writeln('ACYCLIC GRAPH');

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
end.
Code::Blocks
// Badanie cykliczności spójnego grafu nieskierowanego
// Data: 10.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

struct slistEl
{
  slistEl * next;
  int v;
};

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

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

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

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

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

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

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

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

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

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

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

  for(i = 0; i < n; i++) visited[i] = false;  // i zerujemy ją

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

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if(isCyclic(n,A)) cout << "CYCLIC GRAPH";
  else              cout << "ACYCLIC GRAPH";

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;

  return 0;
}
Free Basic
' Badanie cykliczności spójnego grafu nieskierowanego
' Data: 10.12.2013
' (C)2013 mgr Jerzy Wałaszek
'----------------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

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

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

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

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

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

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

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

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

' Funkcja bada cykliczność grafu
'-------------------------------
Function isCyclic(ByVal n As Integer, ByVal G As slistEl Ptr Ptr) As Integer

  Dim As stack S                ' Stos
  Dim As Integer ptr visited    ' Tablica odwiedzin
  Dim As slistEl Ptr p          ' Wskaźnik elementu listy
  Dim As Integer w,v,z,i        ' Zmienne pomocnicze

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

  For i = 0 To n - 1
  	 visited[i] = 0              ' i zerujemy ją
  Next

  S.push(0): S.push(-1)         ' Na stos wierzchołek startowy i -1
  visited[0] = 1                ' Oznaczamy wierzchołek jako odwiedzony

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


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

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

Open Cons For Input As #1

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

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

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

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

Close #1

If isCyclic(n,A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
EndIf

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A

End
Wynik
6 6
0 1
1 2 1 4 1 5
2 3
4 5
CYCLIC GRAPH
6 5
0 1
1 2 1 4
2 3
4 5
ACYCLIC GRAPH

 

Rozwiązanie dla niespójnego grafu nieskierowanego

 Jeśli graf jest niespójny, to składa się z kilku spójnych składowych. W takim przypadku test na cykliczność wykonujemy dla każdej spójnej składowej. Zasada jest następująca:

Tablicę visited tworzymy poza głównym algorytmem i zerujemy ją (algorytm główny tego nie robi). W osobnej zmiennej zapamiętujemy numer wierzchołka startowego (na początku będzie to 0). Następnie uruchamiamy poprzednio opisany algorytm, przekazując do niego numer wierzchołka startowego oraz tablicę visited. Algorytm odwiedza za pomocą DFS wierzchołki spójnej składowej, do której należy wierzchołek startowy. Jednocześnie w tablicy visited są odnotowane wierzchołki odwiedzone. Jeśli algorytm ten wykryje cykl, to zwraca true. W takim przypadku kończymy i również zwracamy true, ponieważ graf jest cykliczny. Jeśli algorytm zwróci false, to przeszukana spójna składowa grafu nie zawiera cyklu. W takim przypadku musimy przeszukać kolejną spójną składową. W tablicy visited szukamy od zapamiętanej pozycji startowej pierwszej komórki, która zawiera wartość false. Odpowiada ona wierzchołkowi, którego algorytm testowania cykliczności nie odwiedził, a zatem wierzchołek ten leży w innej składowej grafu. Uruchamiamy ponownie całą procedurę, przekazując do algorytmu cykliczności numer znalezionego wierzchołka oraz tablicę visited. Jeśli w tablicy visited nie będzie już komórek o wartości false, to cały graf jest przeszukany i nie zawiera cyklu. Kończymy zwracając false.


Algorytm sprawdzania cykliczności niespójnego grafu nieskierowanego

Funkcja isComponentCyclic(graf,v,visited)
Wejście
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
v    numer wierzchołka startowego, v C
visited    n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych
Wyjście:
true – graf jest cykliczny

false – graf nie jest cykliczny

Elementy pomocnicze:
S    stos liczb całkowitych
w,z    wierzchołki robocze, w,v,z C
Lista kroków:
K01: Utwórz pusty stos S  
K02: S.push(v);  S.push(-1) ; na stosie umieszczamy numer wierzchołka startowego i -1
K03: visited[v] ← true ; wierzchołek oznaczamy jako odwiedzony
K04: Dopóki S.empty() = false, wykonuj K05...K09 ; w pętli przechodzimy graf algorytmem DFS
K05:     wS.top(); S.pop() ; w – wierzchołek, z którego przyszliśmy
K06:     vS.top(); S.pop() ; v – wierzchołek bieżący
K07:     Dla każdego sąsiada z wierzchołka v wykonuj K08...K09  
K08:         Jeśli visited[z] = false, to
            S.push(z)
            S.push(v)
            visited[z] ← true
            Następny obieg pętli K07
; jeśli sąsiad nie jest odwiedzony,
; to umieszczamy go na stosie
; wraz z numerem bieżącego wierzchołka
K09:         Jeśli zw, to zakończ z wynikiem true ; trafiliśmy na odwiedzony wierzchołek, z którego nie przyszliśmy
; graf jest cykliczny
K10: Zakończ z wynikiem false ; nigdzie nie natrafiliśmy na odwiedzony wcześniej wierzchołek
; graf nie jest cykliczny
 
Funkcja isCyclic(n,graf)
Wejście
n    liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
true – graf jest cykliczny

false – graf nie jest cykliczny

Elementy pomocnicze:
i    wierzchołek startowy, i C
visited    n elementowa tablica logiczna służąca do zaznaczania wierzchołków odwiedzonych
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Ustaw wszystkie elementy tablicy visited na false  
K03: Dla i = 0,1,...,n-1, wykonuj K04..K05 ; szukamy pierwszego nieodwiedzonego jeszcze wierzchołka
K04:     Jeśli visited[i] = true, to następny obieg pętli K3  
K05:     Jeśli isComponentCyclic(graf,i,visited) = true, to zakończ z wynikiem true ; sprawdzamy cykliczność składowej zawierającej znaleziony wierzchołek
K06: Zakończ z wynikiem false  
 

Program

Ważne:

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

Przykładowe dane dla programu:

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

 

Lazarus
// Badanie cykliczności niespójnego grafu nieskierowanego
// Data: 14.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------------

program project1;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

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

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

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

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

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

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

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

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

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

// Funkcja bada cykliczność składowej grafu
//-----------------------------------------
function isComponentCyclic(var G : TList; v : integer; var visited : array of boolean) : boolean;
var
  S : stack;                    // Stos
  p : PslistEl;                 // Wskaźnik elementu listy
  w,z : integer;                // Zmienne pomocnicze
begin
  S.init;                       // Tworzymy pusty stos
  S.push(v); S.push(-1);        // Na stos wierzchołek startowy i -1
  visited[v] := true;           // Oznaczamy wierzchołek startowy jako odwiedzony
  while S.empty = false do      // W pętli przechodzimy graf za pomocą DFS
  begin
    w := S.top; S.pop;          // Pobieramy ze stosu wierzchołek z którego przyszliśmy
    v := S.top; S.pop;          // oraz wierzchołek bieżący
    p := G[v];                  // Przeglądamy jego listę sąsiadów
    while p <> nil do
    begin
      z := p^.v;                // Numer sąsiada
      if visited[z] = false then
      begin
        S.push(z); S.push(v);   // Sąsiada nieodwiedzonego umieszczamy na stosie
        visited[z] := true;
      end
      else if z <> w then       // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem
      begin                     // z którego przyszliśmy, to odkryliśmy cykl
        S.destroy;
        Exit(true);             // Kończymy z wynikiem true
      end;
      p := p^.next;
    end;
  end;
  S.destroy;
  Exit(false);                  // Kończymy z wynikiem false
end;

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

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if isCyclic(n,A) then writeln('CYCLIC GRAPH')
  else                  writeln('ACYCLIC GRAPH');

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);
end.
Code::Blocks
// Badanie cykliczności niespójnego grafu nieskierowanego
// Data: 14.12.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa i stosu

struct slistEl
{
  slistEl * next;
  int v;
};

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

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

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

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

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

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

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

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

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

// Funkcja bada cykliczność składowej grafu
//-----------------------------------------
bool isComponentCyclic(slistEl ** G, int v, bool * visited)
{
  stack S;                      // Stos
  slistEl * p;                  // Wskaźnik elementu listy
  int w,z;                      // Zmienne pomocnicze

  S.push(v); S.push(-1);        // Na stos wierzchołek startowy i -1
  visited[v] = true;            // Wierzchołek startowy oznaczamy jako odwiedzony
  while(!S.empty())             // W pętli przechodzimy graf za pomocą DFS
  {
    w = S.top(); S.pop();       // Pobieramy ze stosu wierzchołek z którego przyszliśmy
    v = S.top(); S.pop();       // oraz wierzchołek bieżący

    for(p = G[v]; p; p = p->next) // Przeglądamy listę sąsiadów
    {
      z = p->v;                 // Numer sąsiada
      if(!visited[z])
      {
        S.push(z); S.push(v);   // Sąsiada nieodwiedzonego umieszczamy na stosie
        visited[z] = true;
      }
      else if(z != w)           // Jeśli sąsiad jest odwiedzony i nie jest wierzchołkiem
                                // z którego przyszliśmy, to odkryliśmy cykl
        return true;            // Kończymy z wynikiem true
    }
  }
  return false;                 // Kończymy z wynikiem false
}

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

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

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if(isCyclic(n,A)) cout << "CYCLIC GRAPH";
  else              cout << "ACYCLIC GRAPH";

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;

  return 0;
}
Free Basic
' Badanie cykliczności niespójnego grafu nieskierowanego
' Data: 14.12.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa i stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

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

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

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

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

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

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

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

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

' Funkcja bada cykliczność składowej grafu
'-----------------------------------------
Function isComponentCyclic(ByVal G As slistEl Ptr Ptr, ByVal v As Integer, ByVal visited As Integer Ptr) As Integer

  Dim As stack S                ' Stos
  Dim As slistEl Ptr p          ' Wskaźnik elementu listy
  Dim As Integer w,z            ' Zmienne pomocnicze

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

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

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

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

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

Open Cons For Input As #1

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

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

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

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

Close #1

If isCyclic(n,A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
EndIf

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A

End
Wynik
12 11
0 1
1 8
2 3 2 5
3 7
4 9
5 8 5 10
6 9 6 11
7 10
CYCLIC GRAPH
 
12 10
0 1
1 8
2 3 2 5
4 9
5 8 5 10
6 9 6 11
7 10
ACYCLIC GRAPH

 

Rozwiązanie dla grafu skierowanego

Przy grafie skierowanym postępujemy podobnie jak przy grafie niespójnym. Chodzi o to, że z uwagi na kierunkowość krawędzi przejście DFS od wybranego wierzchołka nie gwarantuje nam odwiedzenia wszystkich wierzchołków w grafie, a te nieodwiedzone wierzchołki mogą tworzyć cykle. Istnieje również drugi problem: w grafie skierowanym DFS może ponownie odwiedzać określony wierzchołek, a mimo to nie będzie cyklu. Przyjrzyjmy się poniższemu rysunkowi:

 

 

Jeśli przejście DFS wyruszy od wierzchołka 0, to dotrze do wierzchołka 3 dwoma drogami (niebieską i czerwoną). Jeśli pierwsza będzie droga niebieska, to DFS ustawi wierzchołek 3 jako odwiedzony. Następnie wyruszy drogą czerwoną i w wierzchołku 2 stwierdzi, że istnieje krawędź do już odwiedzonego wcześniej wierzchołka 3. Wg kryterium dla grafu nieskierowanego oznacza to cykl. Jak widzimy, tutaj to kryterium zawodzi, ponieważ cykl nie istnieje. Wniosek jest tylko jeden: dla grafu skierowanego musimy przyjąć inne kryterium wykrywania cyklu.

Umówmy się, że wierzchołki grafu będą mogły znajdować się w trzech stanach pamiętanych przez tablicę odwiedzin:

W grafie skierowanym cykl istnieje tylko wtedy, gdy krawędź wiedzie do wierzchołka przetwarzanego (szarego). Wierzchołki już przetworzone nie mogą tworzyć cyklu (gdyby tak było, to algorytm znalazł by już ten cykl wcześniej i zakończył swoje działanie, nieprawdaż?). Prześledźmy to na prostym przykładzie.

 

Mamy dany graf skierowany. Umówmy się, że DFS będzie go przechodzić wg kolejnych numerów wierzchołków.

Początkowo wszystkie wierzchołki są białe.

Przejście DFS rozpoczynamy od wierzchołka 0. Zmieniamy jego kolor na szary (oznaczający wierzchołek w trakcie przetwarzania). Posiada on trzech sąsiadów: wierzchołki 1, 2 i 3, które odwiedzamy rekurencyjnie w tej kolejności.
Przechodzimy do wierzchołka 1. Zmieniamy jego kolor na szary. Wierzchołek posiada tylko jednego sąsiada: wierzchołek nr 2.
Przechodzimy do wierzchołka 2. Ponieważ wierzchołek ten nie posiada dalszych sąsiadów, zmieniamy jego kolor na czarny (oznaczający zakończenie przetwarzania wierzchołka).
 Wracamy do wierzchołka 1. Wierzchołek nie posiada dalszych sąsiadów. Zmieniamy jego kolor na czarny.
Wracamy do wierzchołka 0. Posiada on wciąż dwóch sąsiadów do zbadania: wierzchołki 2 i 3.
Do wierzchołka 2 nie przechodzimy, ponieważ ma kolor czarny (odwiedzamy tylko wierzchołki białe, a napotkanie wierzchołka szarego sygnalizuje cykl). Zatem kolejnym do odwiedzenia wierzchołkiem będzie wierzchołek 3.
Idziemy do wierzchołka 3. Kolorujemy go na szaro. Kolejnym do odwiedzenia sąsiadem jest wierzchołek 4.
Idziemy do wierzchołka 4. Kolorujemy go na szaro. Następnym do odwiedzenia jest wierzchołek 5.
Jesteśmy w wierzchołku 5. Kolorujemy go na szaro. Wykrywamy, że sąsiad 3 jest szary. Oznacza to istnienie cyklu. Kończymy algorytm z wynikiem pozytywnym – graf jest cykliczny.

 

Algorytm sprawdzania cykliczności grafu skierowanego

Algorytm rekurencyjnej funkcji isGraphCyclic
Wejście
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
v    numer wierzchołka startowego, v C
visited    n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych
Wyjście:
true – graf jest cykliczny

false – graf nie jest cykliczny

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 K03...K05  
K03:     Jeśli visited[u] = czarny, to następny obieg pętli K02 ; wierzchołki przetworzone ignorujemy
K04:     Jeśli visited[u] = szary, to zakończ z wynikiem true  ; cykl znaleziony, kończymy
K05:     Jeśli isGraphCyclic(graf,u,visited) = true, to zakończ z wynikiem true ; wywołanie rekurencyjne dla sąsiada u
K06: visited[v] ← czarny ; wierzchołek przetworzony, ustawiamy kolor czarny
K07: Zakończ z wynikiem false ; nie było cyklu
 
Algorytm funkcji isCyclic(n,graf)
Wejście
n    liczba wierzchołków w grafie, n C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje
Wyjście:
true – graf jest cykliczny

false – graf nie jest cykliczny

Elementy pomocnicze:
i    wierzchołek startowy, i C
visited    n elementowa tablica całkowita służąca do zaznaczania wierzchołków odwiedzonych
Lista kroków:
K01: Utwórz n elementową tablicę visited  
K02: Ustaw wszystkie elementy tablicy visited na biało  
K03: Dla i = 0,1,...,n-1, wykonuj K04..K05 ; szukamy pierwszego nieodwiedzonego jeszcze wierzchołka
K04:     Jeśli visited[i] biały, to następny obieg pętli K3 ; pomijamy wierzchołki już przetworzone
K05:     Jeśli isGraphCyclic(graf,i,visited) = true, to zakończ z wynikiem true ; sprawdzamy cykliczność składowej zawierającej znaleziony wierzchołek
K06: Zakończ z wynikiem false  

 

Kolory możemy kodować liczbami lub nawet znakami (znaki ASCII zajmują 1 bajt pamięci) : 'b', 0 (biały); 's', 1 (szary) i 'c', 2 (czarny).

Program

Ważne:

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

Przykładowe dane dla programu:

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

 

Lazarus
// Badanie cykliczności grafu skierowanego
// Data: 19.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

program project1;

// Typy dla dynamicznej tablicy list sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

TList = array of PslistEl;

// Funkcje badające cykliczność grafu
//-----------------------------------
function isGraphCyclic(var G : TList; v : integer; var visited : array of char) : boolean;
var
  p : PslistEl;                 // Wskaźnik elementu listy
  u : integer;
begin
  visited[v] := 'G';            // Kolorujemy wierzchołek na szaro
  p := G[v];                    // Sprawdzamy kolejnych sąsiadów
  while p <> nil do
  begin
    u := p^.v;                  // u <-- numer sąsiada
    if visited[u] = 'G' then Exit(true); // Sąsiad szary - mamy cykl. przerywamy
    if (visited[u] = 'W') and
       isGraphCyclic(G,u,visited) then Exit(true); // Wywołanie rekurencyjne
    p := p^.next;
  end;
  visited[v] := 'B';             // Kolorujemy wierzchołek na czarno
  Exit(false);
end;

function isCyclic(n : integer; var G : Tlist) : boolean;
var
  i : integer;
  visited : array of char;
begin
  SetLength(visited,n);  // Tworzymy tablicę odwiedzin
  for i := 0 to n - 1 do
    visited[i] := 'W';   // Tablicę zerujemy
  for i := 0 to n - 1 do
    if (visited[i] = 'W') and
       isGraphCyclic(G,i,visited) then Exit(true);
  Exit(false);
end;

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if isCyclic(n,A) then writeln('CYCLIC GRAPH')
  else                  writeln('ACYCLIC GRAPH');

  // Usuwamy tablicę list sąsiedztwa

  for i := 0 to n - 1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;

  SetLength(A,0);

end.
Code::Blocks
// Badanie cykliczności grafu skierowanego
// Data: 19.12.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

struct slistEl
{
  slistEl * next;
  int v;
};

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

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

bool isCyclic(int n, slistEl ** G)
{
  int i;
  char * visited;

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

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

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

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

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

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

  if(isCyclic(n,A)) cout << "CYCLIC GRAPH";
  else              cout << "ACYCLIC GRAPH";

  cout << endl;

  // Usuwamy tablicę list sąsiedztwa

  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] A;

  return 0;
}
Free Basic
' Badanie cykliczności grafu skierowanego
' Data: 19.12.2013
' (C)2013 mgr Jerzy Wałaszek
'----------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

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

Const WHITE = 0
Const GRAY = 1
Const BLACK = 2
 
Function isGraphCyclic(ByVal G As slistEl Ptr Ptr,_
	                    ByVal v As Integer, _
	                    ByVal visited As Byte Ptr) As Integer

  Dim As slistEl ptr p          ' Wskaźnik elementu listy
  Dim As Integer u

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

Function isCyclic(ByVal n As integer, ByVal G As slistEl Ptr Ptr) As Integer
  Dim As Integer i
  Dim As Byte Ptr visited

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

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

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

Open Cons For Input As #1

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

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

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

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

Close #1

If isCyclic(n,A) Then
  Print "CYCLIC GRAPH"
Else
  Print "ACYCLIC GRAPH"
EndIf

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A

End
Wynik
6 7
0 1 0 2 0 3
1 2
3 4
4 5
5 3
CYCLIC GRAPH
 
6 7
0 1 0 2 0 3
1 2
3 4 3 5
4 5
ACYCLIC GRAPH

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.