Znajdowanie cykli w grafie


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 grafu nieskierowanego
Rozwiązanie dla grafu skierowanego

Problem 1

Dla każdego wierzchołka grafu 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.

Elementy 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 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) (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ę.
Elementy 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 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 K09...K10 ; wypisujemy wierzchołki tworzące cykl
K09:         uS.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).

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

 

Przykładowe dane dla programu:

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

 

Lazarus
// 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, jesli istnieje
      begin
        u := S.top; S.pop;         // Pobieramy ze stosu numer wierzcjoł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.
Code::Blocks
// 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, jesli istnieje
      {
        u = S.top(); S.pop();      // Pobieramy ze stosu numer wierzcjoł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;
}
Free 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, jesli istnieje
      u = S.top(): S.pop()         ' Pobieramy ze stosu numer wierzcjoł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

 

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.

Elementy 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 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) (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ę.
Elementy 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 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 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).

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

 

Przykładowe dane dla programu:

       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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 



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.