Istnienie cyklu lub ścieżki Eulera


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

Zbadać, czy dany graf posiada cykl lub ścieżkę Eulera.

 

 

Rozwiązanie dla grafu nieskierowanego

Ścieżka Eulera (ang Eulerian path) jest ścieżką w grafie, która przechodzi dokładnie jeden raz przez każdą jego krawędź. Aby taka ścieżka istniała, graf musi być spójny (z pominięciem wierzchołków  o stopniu 0, czyli bez krawędzi) oraz każdy jego wierzchołek za wyjątkiem dwóch musi posiadać parzysty stopień.

 

Graf ze ścieżką Eulera:

graf ze ścieżką Eulera

       Graf bez ścieżki Eulera:

graf bez ścieżki Eulera

Graf jest półeulerowski (ang. semi-Eulerian graph), jeśli zawiera ścieżkę Eulera.

 

Cykl Eulera (ang. Eulerian cycle) jest ścieżką w grafie, która przechodzi przez wszystkie jego krawędzie i kończy się w wierzchołku startowym. Aby istniał cykl Eulera, graf musi być spójny (z pominięciem wierzchołków  o stopniu 0) oraz każdy jego wierzchołek musi posiadać stopień parzysty.

Graf z cyklem Eulera:

graf z cyklem Eulera

       Graf bez cyklu Eulera:

graf bez cyklu Eulera

 

Graf jest eulerowski (ang. Eulerian graph), jeśli zawiera cykl Eulera.

 

Algorytm jest następujący:

 

Przeglądamy kolejne wierzchołki grafu aż do momentu, gdy natrafimy na wierzchołek o niezerowej liczbie sąsiadów. To będzie nasz punkt startowy. Tworzymy licznik wierzchołków o nieparzystym stopniu i zerujemy go. Od tego wierzchołka uruchamiamy przejście DFS, które odwiedzi wszystkie wierzchołki, do których istnieją w grafie ścieżki z wierzchołka startowego. Zatem wyznaczy spójną składową zawierającą wierzchołek startowy. Przejście DFS pozwoli nam sprawdzić, czy graf jest spójny. W trakcie przechodzenia grafu DFS zlicza sąsiadów każdego odwiedzanego wierzchołka i, jeśli liczba ta jest nieparzysta, to zwiększa licznik wierzchołków o nieparzystym stopniu. Gdy przejście DFS się zakończy, kontynuujemy przeglądanie grafu od następnego wierzchołka po wierzchołku startowym. Jeśli natrafimy na nieodwiedzony wierzchołek, który posiada sąsiadów, to będzie to oznaczało, że graf nie jest spójny i nie może posiadać cyklu lub ścieżki Eulera. W takim przypadku kończymy algorytm z wynikiem negatywnym. Jeśli takiego wierzchołka nie spotkamy, to graf jest spójny (lub posiada dodatkowo jedynie wierzchołki bez krawędzi). W takim razie cykl Eulera będzie istniał w grafie, jeśli licznik wierzchołków o nieparzystym stopniu ma wartość 0. Jeśli licznik ten ma wartość 2, to będzie istniała ścieżka Eulera. W przeciwnym razie algorytm kończymy z wynikiem negatywnym.

 

Algorytm badający istnienie ścieżki lub cyklu Eulera w grafie nieskierowanym

Wejście
n    liczba wierzchołków w grafie, n symbol C
graf    zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf nie może posiadać pętli.
Wyjście:
Wynik:

    0 – graf nie zawiera ścieżki lub cyklu Eulera
    1 – graf zawiera ścieżkę Eulera, lecz nie zawiera cyklu Eulera.
    2 – graf zawiera cykl Eulera

Elementy pomocnicze:
no  –  liczba wierzchołków o nieparzystym stopniu, no symbol C
i,v,u  –  wierzchołki grafu, i,v,u symbol C
nc  –  zlicza sąsiadów, nc symbol C
S  –  stos wierzchołków
visited  –  n elementowa tablica logiczna odwiedzin
Lista kroków:
K01: Znajdź pierwszy wierzchołek i o stopniu niezerowym  
K02: Jeśli nie istnieje taki wierzchołek, zakończ z wynikiem 1 ; graf nie ma krawędzi, kończymy
K03: Utwórz n elementową tablicę visited  
K04: Tablicę visited wypełnij wartościami false  
K05: Twórz pusty stos S  
K06: no ← 0 ; zerujemy licznik wierzchołków o nieparzystym stopniu
K07: S.push(i) ; zapamiętujemy wierzchołek i-ty na stosie
K08: visited[i] ← true ; oznaczamy wierzchołek jako odwiedzony
K09: Dopóki S.empty() = false, wykonuj K10...K17 ; uruchamiamy DFS, aby sprawdzić spójność oraz wyznaczyć stopnie wierzchołków
K10:     vS.top(); S.pop() ; pobieramy wierzchołek ze szczytu stosu
K11:     nc ← 0 ; zerujemy licznik sąsiadów
K12:     Dla każdego sąsiada u wierzchołka v wykonuj K13...K16 ; przeglądamy sąsiadów
K13:         ncnc + 1 ; zwiększamy licznik sąsiadów
K14:         Jeśli visited[u] = true, to następny obieg pętli K12 ; szukamy nieodwiedzonego sąsiada
K15:         visited[u] ← true ; zaznaczamy go jako odwiedzonego
K16:         S.push(u) ; i umieszczamy na stosie
K17:     Jeśli nc jest nieparzyste, to nono + 1 ; zwiększamy licznik wierzchołków o stopniu nieparzystym
K18: Dla v = i+1, i+2,...,n-1: wykonuj K19 ; szukamy nieodwiedzonego jeszcze wierzchołka
K19:     Jeśli (visited[v] = false) symbol (v ma sąsiada), zakończ z wynikiem 0 ; graf jest niespójny
K20: Jeśli no = 0, to zakończ z wynikiem 2 ; liczba wierzchołków o nieparzystym stopniu równa zero
K21 Jeśli no = 2, to zakończ z wynikiem 1 ; dwa wierzchołki o nieparzystym stopniu
K22: Zakończ z wynikiem 0 ; brak cyklu lub ścieżki Eulera

 

Zastanów się, jak zmodyfikować powyższy algorytm, aby uwzględniał również pętle (pętlę należy liczyć za dwie krawędzie).

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 sprawdza istnienie w nim ścieżki lub cyklu Eulera. Wynik jest wypisywany w oknie konsoli:

 

NOT AN EULERIAN GRAPH
SEMI-EULERIAN GRAPH
EULERIAN GRAPH

 

Przykładowe dane dla programu:

Graf z cyklem Eulera

symbol

12 14
1 2 1 4
2 4 2 5 2 7
4 5 4 6 4 7 4 9
5 7 5 11
6 7
7 9 7 11
       Graf ze ścieżką Eulera

symbol

12 16
0 1
1 4
2 3 2 4 2 5 2 7
4 5 4 6 4 7 4 9
5 10 5 11
6 9
7 9 7 11
9 10
       Graf bez ścieżki i cyklu Eulera

symbol

12 17
0 1
1 4
2 3 2 4 2 5 2 7
4 5 4 6 4 7 4 9
5 6 5 10 5 11
6 9
7 9 7 11
9 10

 

Lazarus
// Badanie, czy graf zawiera cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------------------

program eulercp;

// 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 graf pod kątem posiadania cyklu lub ścieżki Eulera
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// 0 - graf nie zawiera ścieżki lub cyklu Eulera
// 1 - graf zawiera ścieżkę Eulera
// 2 - graf zawiera cykl Eulera
//-----------------------------------------------------------------
function isEulerian(n : integer; var graf : TList) : integer;
var
  no,nc,i,v,u : integer;
  S           : stack;
  visited     : array of boolean;
  p           : PslistEl;

begin
  i := 0;                     // Szukamy pierwszego wierzchołka z sąsiadami
  while (i < n) and (graf[i] = nil) do inc(i);
  if i = n then Exit(1);      // Graf nie ma krawędzi

  SetLength(visited,n);       // Tworzymy dynamicznie tablicę odwiedzin
  for v := 0 to n - 1 do      // Wypełniamy ją wartościami false
    visited[v] := false;

  S.init;                     // Tworzymy stos

  no := 0;                    // Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push(i);                  // Wierzchołek startowy na stos
  visited[i] := true;         // oznaczamy go jako odwiedzony

  // Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  // wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  // liczbę wierzchołków o stopniach nieparzystych

  while S.empty = false do
  begin
    v := S.top;               // Pobieramy do v wierzchołek ze stosu
    S.pop;                    // Pobrany wierzchołek usuwamy ze stosu

    nc := 0;                  // Licznik sąsiadów na zero

    p := graf[v];             // Przeglądamy sąsiadów wierzchołka v
    while p <> nil do
    begin
      inc(nc);                // Zwiększamy licznik sąsiadów
      u := p^.v;
      if not visited[u] then  // Szukamy nieodwiedzonych sąsiadów
      begin
        visited[u] := true;   // Zaznaczamy ich jako odwiedzonych
        S.push(u);            // i umieszczamy na stosie
      end;
      p := p^.next;           // Przechodzimy do następnego sąsiada na liście
    end;

    if nc mod 2 = 1 then inc(no); // Nieparzysta liczba sąsiadów?
  end;

  for v := i + 1 to n - 1 do  // Przeglądamy pozostałe wierzchołki grafu
    if (visited[v] = false) and (graf[v] <> nil) then
    begin
      SetLength(visited,0);   // Usuwamy tablicę odwiedzin
      Exit(0);                // graf nie jest spójny
    end;

  SetLength(visited,0);       // Usuwamy tablicę odwiedzin

  if no = 0 then Exit(2);     // Graf zawiera cykl Eulera

  if no = 2 then Exit(1);     // Graf zawiera ścieżkę Eulera

  Exit(0);                    // Graf nie posiada ścieżki lub cyklu Eulera
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

  // Tablicę 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;

  case isEulerian(n,A) of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;

  // 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, czy graf zawiera cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (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 graf pod kątem posiadania cyklu lub ścieżki Eulera
// n    - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// 0 - graf nie zawiera ścieżki lub cyklu Eulera
// 1 - graf zawiera ścieżkę Eulera
// 2 - graf zawiera cykl Eulera
//-----------------------------------------------------------------
int isEulerian(int n, slistEl ** graf)
{
  int no,nc,i,v,u;
  stack S;
  bool * visited;
  slistEl *p;

  for(i = 0; i < n && !graf[i]; i++); // Szukamy pierwszego wierzchołka z sąsiadami

  if(i == n) return 1;        // Graf nie ma krawędzi

  visited = new bool [n];     // Tworzymy dynamicznie tablicę odwiedzin
  for(v = 0; v < n; v++)      // Wypełniamy ją wartościami false
    visited[v] = false;

  no = 0;                     // Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push(i);                  // Wierzchołek startowy na stos
  visited[i] = true;          // oznaczamy go jako odwiedzony

  // Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  // wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  // liczbę wierzchołków o stopniach nieparzystych

  while(!S.empty())
  {
    v = S.top();              // Pobieramy do v wierzchołek ze stosu
    S.pop();                  // Pobrany wierzchołek usuwamy ze stosu

    nc = 0;                   // Licznik sąsiadów na zero

    for(p = graf[v]; p; p = p->next) // Przeglądamy sąsiadów wierzchołka v
    {
      nc++;                   // Zwiększamy licznik sąsiadów
      u = p->v;
      if(!visited[u])         // Szukamy nieodwiedzonych sąsiadów
      {
        visited[u] = true;    // Zaznaczamy ich jako odwiedzonych
        S.push(u);            // i umieszczamy na stosie
      }
    }

    if(nc % 2 == 1) no++;     // Nieparzysta liczba sąsiadów?
  }

  for(v = i + 1; v < n; v++)  // Przeglądamy pozostałe wierzchołki grafu
    if(!visited[v] && graf[v])
    {
      delete [] visited;      // Usuwamy tablicę odwiedzin
      return 0;               // graf nie jest spójny
    }

  delete [] visited;          // Usuwamy tablicę odwiedzin

  if(!no) return 2;           // Graf zawiera cykl Eulera

  if(no == 2) return 1;       // Graf zawiera ścieżkę Eulera

  return 0;                   // Graf nie posiada ścieżki lub cyklu Eulera
}

// **********************
// *** 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

  // Tablicę 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;

  switch(isEulerian(n,A))
  {
    case 0: cout << "NOT AN EULERIAN GRAPH\n";
            break;
    case 1: cout << "SEMI-EULERIAN GRAPH\n";
            break;
    case 2: cout << "EULERIAN GRAPH\n";
            break;
  }

  // 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, czy graf zawiera cykl lub ścieżkę Eulera
' Data: 4.01.2014
' (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 graf pod kątem posiadania cyklu lub ścieżki Eulera
' n    - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' Wynik:
' 0 - graf nie zawiera ścieżki lub cyklu Eulera
' 1 - graf zawiera ścieżkę Eulera
' 2 - graf zawiera cykl Eulera
'-----------------------------------------------------------------
Function isEulerian(ByVal n As integer, byval graf As slistEl Ptr Ptr) As Integer

  Dim As Integer no,nc,i,v,u
  Dim As stack S
  Dim As Byte Ptr visited
  Dim As slistEl Ptr p

  i = 0
  while (i < n) AndAlso (graf[i] = 0)
  	 i += 1                    ' Szukamy pierwszego wierzchołka z sąsiadami
  Wend

  If i = n Then Return 1      ' Graf nie ma krawędzi

  visited = New Byte [n]      ' Tworzymy dynamicznie tablicę odwiedzin
  For v = 0 To n - 1          ' Wypełniamy ją wartościami false
    visited[v] = 0
  Next
  
  no = 0                      ' Zerujemy licznik wierzchołków o stopniu nieparzystym

  S.push(i)                   ' Wierzchołek startowy na stos
  visited[i] = 1              ' oznaczamy go jako odwiedzony

  ' Uruchamiamy przejście DFS, aby wyznaczyć spójną składową zawierającą
  ' wierzchołek startowy oraz policzyć stopnie wierzchołków i wyznaczyć
  ' liczbę wierzchołków o stopniach nieparzystych

  While S.empty() = 0
    v = S.top()               ' Pobieramy do v wierzchołek ze stosu
    S.pop()                   ' Pobrany wierzchołek usuwamy ze stosu

    nc = 0                    ' Licznik sąsiadów na zero

    p = graf[v]               ' Przeglądamy sąsiadów wierzchołka v
    While p 
      nc += 1                 ' Zwiększamy licznik sąsiadów
      u = p->v
      If visited[u] = 0 Then  ' Szukamy nieodwiedzonych sąsiadów
        visited[u] = 1        ' Zaznaczamy ich jako odwiedzonych
        S.push(u)             ' i umieszczamy na stosie
      End If
      p = p->Next             ' Następny sąsiad na liście
    Wend

    If nc Mod 2 = 1 Then no += 1 ' Nieparzysta liczba sąsiadów?
  Wend

  For v = i + 1 To n - 1      ' Przeglądamy pozostałe wierzchołki grafu
    If (visited[v] = 0) AndAlso (graf[v] <> 0) Then
      Delete [] visited       ' Usuwamy tablicę odwiedzin
      Return 0                ' graf nie jest spójny
    End If
  Next

  Delete [] visited           ' Usuwamy tablicę odwiedzin

  If no = 0 Then Return 2     ' Graf zawiera cykl Eulera

  If no = 2 Then return 1     ' Graf zawiera ścieżkę Eulera

  Return 0                    ' Graf nie posiada ścieżki lub cyklu Eulera
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

Print

Select Case isEulerian(n,A)
  case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2
    Print "EULERIAN GRAPH"
End Select

' 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 14
1 2 1 4
2 4 2 5 2 7
4 5 4 6 4 7 4 9   
5 7 5 11
6 7
7 9 7 11

EULERIAN GRAPH
12 16
0 1
1 4
2 3 2 4 2 5 2 7
4 5 4 6 4 7 4 9   
5 10 5 11
6 9
7 9 7 11
9 10

SEMI-EULERIAN GRAPH
12 17
0 1
1 4
2 3 2 4 2 5 2 7
4 5 4 6 4 7 4 9
5 6 5 10 5 11
6 9
7 9 7 11
9 10

NOT AN EULERIAN GRAPH

 

Rozwiązanie dla grafu skierowanego

W grafie skierowanym istnieje cykl Eulera jeśli

Ścieżka Eulera istnieje wtedy, gdy:

Z podanych powyżej informacji wynika, iż kluczowym warunkiem istnienia w grafie skierowanym cyklu lub ścieżki Eulera jest to, aby graf był silnie spójny poza wierzchołkami, które nie są incydentne z żadną krawędzią. Do rozwiązania tego problemu wykorzystamy nieco zmodyfikowany algorytm Tarjana wyznaczający silnie spójne składowe grafu. W trakcie przechodzenia przez graf procedura DFS będzie zbierała informacje o stopniach wejściowych i wyjściowych każdego wierzchołka oraz wyznaczała silnie spójne składowe, zapisując w tablicy C ich numery dla każdego z wierzchołków grafu. Następnie wyszukamy pierwszy wierzchołek o niezerowym stopniu. Wartość elementu tablicy C dla tego wierzchołka określi numer silnie spójnej składowej. Tworzymy liczniki: cinout, coutin, które będą zliczać wierzchołki o stopniach wchodzącym i wychodzącym różniących się o 1. Liczniki te zerujemy. Przeglądniemy wierzchołki wg poniższych zasad:

  1. Stopienie wchodzący i wychodzący równe zero – kontynuujemy z następnym wierzchołkiem.
  2. Wierzchołek musi należeć do silnie spójnej składowej. Jeśli nie, to graf nie jest silnie spójny, co daje wynik negatywny.
  3. Stopień wchodzący równy wychodzącemu – kontynuujemy z następnym wierzchołkiem.
  4. Jeśli stopień wchodzący - stopień wychodzący = 1, to zwiększ licznik cinout o 1. Jeśli cinout > 1, to zakończ z wynikiem negatywnym.
  5. Jeśli stopień wychodzący - stopień wchodzący = 1, to zwiększ licznik coutin o 1. Jeśli coutin > 1, to zakończ z wynikiem negatywnym.
  6. Jeśli stopnie różnią się więcej niż o 1, zakończ z wynikiem negatywnym

Gdy algorytm zakończy bez wyniku negatywnego przeglądanie wierzchołków grafu, to sprawdzamy stan liczników:

 

cinout = 1 i coutin = 1 – jest ścieżka Eulera (wystarczy sprawdzić tylko jeden z nich)

Inaczej mamy cykl Eulera

 

Algorytm badający istnienie ścieżki lub cyklu Eulera w grafie skierowanym

Algorytm przejścia DFSscc(v,cvn,VN,VLow,VS,Vind,Voutd,C,S,graf)
Wszystkie parametry za wyjątkiem v mogą być zrealizowane jako globalne, co zmniejszy zapotrzebowanie na pamięć przy wywoływaniach rekurencyjnych.
Wejście
v  –  wierzchołek startowy, v C
cvn  –  numer bieżącego wierzchołka, cvn C
VN  –  tablica numerów wierzchołków, które ustala DFSscc()
VLow  –  tablica parametrów Low
VS  –  tablica logiczna, która informuje, czy dany wierzchołek jest na stosie S
Vind  –  tablica stopni wchodzących wierzchołków
Voutd  –  tablica stopni wychodzących wierzchołków
C  –  tablica numerów składowych, do których należą wierzchołki
S  –  stos wierzchołków
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
Ustawione tablice: C, Vind i Vout.
Elementy pomocnicze:
u  –  wierzchołek, u C
Lista kroków:
K01: cvncvn + 1 ; zwiększamy numer wierzchołka
K02: VN[v] ← cvn ; i zapamiętujemy go w tablicy VN
K03: VLow[v] ← cvn ; oraz wstępnie w tablicy VLow
K04: S.push(v) ; wierzchołek umieszczamy na stosie
K05: VS[v] ← true ; i zapamiętujemy w VS, że jest on na stosie
K06: Dla każdego sąsiada u wierzchołka v wykonuj K07...K14 ; przeglądamy kolejnych sąsiadów wierzchołka v
K07     Voutd[v] ← Voutd[v] + 1 ; obliczamy stopień wychodzący wierzchołka v
K08     Vind[u] ← Vind[u] + 1 ; i stopień wchodzący wierzchołka u
K09:     Jeśli VN[u] = 0, to idź do K13 ; sprawdzamy, czy wierzchołek był odwiedzony
K10:     Jeśli VS[u] = false, to następny obieg pętli K06 ; sprawdzamy, czy wierzchołek u jest na stosie
K11:     VLow[v] ← min(VLow[v], VN[u]) ; jeśli tak, to wyznaczamy najmniejszy numer dostępnego wierzchołka z v
K12:     Następny obieg pętli K06 ; i kontynuujemy pętlę
K13:     DFSscc(u,cvn,VN,VLow,VS,S,Lscc,graf) ; wierzchołek nieodwiedzony: rekurencyjnie wywołujemy dla niego DFSscc()
K14:     VLow[v] ← min(VLow[v], VLow[u]) ; i wyznaczamy najmniejszy numer dostępnego wierzchołka z v
K15: Jeśli VLow[v] ≠ VN[v], to zakończ ; sprawdzamy, czy znaleźliśmy całą silnie spójną składową
K16:     uS.top() ; pobieramy ze stosu wierzchołek silnie spójnej składowej
K17:     S,pop() ; pobrany wierzchołek usuwamy ze stosu
K18:     VS[u] ← false ; zaznaczamy, że wierzchołka już nie ma na stosie
K19:     C[u] ← v ; w tablicy C zaliczamy wierzchołek u do składowej v
K20: Jeśli uv, to idź do K16 ; pętlę kontynuujemy, aż do dotarcia do korzenia składowej
K21: Zakończ  

 

Algorytm główny: isEulerian(n,graf)
Wejście
n  –  liczba wierzchołków w grafie, n C
graf  –  graf zadany w dowolny sposób, algorytm tego nie precyzuje
Wyjście:
0 – graf nie posiada cyklu i ścieżki Eulera
1 – graf posiada ścieżkę Eulera
2 – graf posiada cykl Eulera
Elementy pomocnicze:
v  –  numer wierzchołka, v C
cvn  –  numer bieżącego wierzchołka lub spójnej składowej, cvn C
VN  –  tablica numerów wierzchołków, które ustala DFSscc()
VLow  –  tablica parametrów Low
VS  –  tablica logiczna, która informuje, czy dany wierzchołek jest na stosie S
S  –  stos wierzchołków
Vind  –  tablica stopni wchodzących
Voutd  –  tablica stopni wychodzących
C  –  tablica numerów składowych, do których należą wierzchołki
cinout  –  licznik wierzchołków o większych stopniach wchodzących, cinout C
coutin  –  licznik wierzchołków o większych stopniach wychodzących, coutin C
Lista kroków:
K01: Utwórz n elementowe tablice:
VN, VLow, VS, Vind, Voutd i C
 
K02: Wyzeruj tablice:
VN, VS, Vind i Vout
 
K03: Utwórz pusty stos S  
K04: cvn ← 0 ; zerujemy numer startowy wierzchołków dla DFS
K05: Dla v = 0,1,...,n-1, wykonuj
    Jeśli VN[v] = 0, to DFSscc(v,cvn,VN,VLow,VS,Vind,Voutd,C,S,graf)
; w nieodwiedzonym wierzchołku uruchamiamy DFS
K06: v ← 0  
K07: Dopóki (v < n) (Vind[v] + Vout[v] = 0) wykonuj vv + 1 ; szukamy wierzchołka o niezerowym stopniu
K08: Jeśli v = n, to zakończ z wynikiem 0 ; graf jest pusty
K09: cvnC[v] ; zapamiętujemy numer składowej, do której należy v
K10: cinout ← 0 ; zerujemy liczniki
K11: coutin ← 0  
K12: Dopóki v < n wykonuj K13...K23 ; przechodzimy przez wierzchołki grafu
K13:     Jeśli Vind[v] + Voutd[v] = 0, to idź do K23 ; pomijamy wierzchołki o stopniu zerowym
K14:     Jeśli C[v] ≠ cvn, to zakończ z wynikiem 0 ; graf nie jest silnie spójny
K15:     Jeśli Vind[v] = Voutd[v], to idź do K23 ; pomijamy wierzchołki o stopniach równych
K16:     Jeśli Vind[v] - Voutd[v] ≠ 1, to idź do K21 ; różnica stopnia wchodzącego i wychodzącego = 1?
K17:     cinoutcinout + 1 ; jeśli tak, zwiększamy odpowiedni licznik
K18:     Jeśli cinout > 1, to zakończ z wynikiem 0 ; licznik nie może być większy od 1
K19:     Idź do K23  
K20:     Jeśli Voutd[v] - Vind[v] ≠ 1, to zakończ z wynikiem 0 ; stopnie zbytnio się różnią
K21:     coutincoutin + 1 ; zwiększamy odpowiedni licznik
K22:     Jeśli coutin > 1, to zakończ z wynikiem 0 ; który również nie może być większy od 1
K23:     vv + 1 ; następny wierzchołek
K24: Jeśli cinout = 1, to zakończ z wynikiem 1 ; jest ścieżka Eulera
K25: Zakończ z wynikiem 2 ; lub cykl Eulera

 

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 sprawdza istnienie w nim ścieżki lub cyklu Eulera. Wynik jest wypisywany w oknie konsoli:

 

NOT AN EULERIAN GRAPH
SEMI-EULERIAN GRAPH
EULERIAN GRAPH

 

Przykładowe dane dla programu:

Graf z cyklem Eulera

symbol

9 17
0 1
1 3 1 4
2 1 2 5
3 0 3 2 3 7
4 2 4 3 4 6
5 4 5 7
6 3
7 4 7 8
8 5
       Graf ze ścieżką Eulera

symbol

9 17
0 1 0 7
1 2 1 5
2 3 2 4
3 0 3 7
4 5 4 8
5 2 5 7
6 3
7 4 7 6 7 8
8 1
       Graf bez ścieżki i cyklu Eulera

symbol

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

 

Lazarus
// Badanie istnienia cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program scc;

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

// 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;

// Zmienne globalne
//-----------------
var
  n,m,cvn: integer;
  VN,VLow,Vind,Voutd,C  : array of integer;
  VS       : array of boolean;
  S        : stack;
  graf     : array of PslistEl;

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

// 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;

// Zwraca mniejszą z dwóch liczb
//------------------------------
function min(a,b : integer) : integer;
begin
  if a < b then min := a else min := b;
end;

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową oraz stopnie wierzchołków
// v - wierzchołek startowy dla DFS
//---------------------------------------------------
procedure DFSscc(v : integer);
var
  u : integer;
  p : PslistEl;
begin
  inc(cvn);                     // Zwiększamy numer wierzchołka
  VN[v]    := cvn;              // Numerujemy bieżący wierzchołek
  VLow[v]  := cvn;              // Ustalamy wstępnie parametr Low
  S.push(v);                    // Wierzchołek na stos
  VS[v]    := true;             // Zapamiętujemy, że v jest na stosie

  p := graf[v];                 // Przeglądamy listę sąsiadów
  while p <> nil do
  begin
    inc(Voutd[v]);              // Wyznaczamy stopień wychodzący
    inc(Vind[p^.v]);            // i wchodzący
    if VN[p^.v] = 0 then        // Jeśli sąsiad jest nieodwiedzony, to
    begin
      DFSscc(p^.v);             // wywołujemy dla niego rekurencyjnie DFS
      VLow[v] := min(VLow[v],VLow[p^.v]); // i obliczamy parametr Low dla v
    end
    else if VS[p^.v] then       // jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] := min(VLow[v],VN[p^.v]); // to wyznaczamy parametr Low dla v
    p := p^.next;
  end;

  if VLow[v] = VN[v] then       // Sprawdzamy, czy mamy kompletną składową
  begin
    repeat
      u := S.top;               // Pobieramy wierzchołek ze stosu
      S.pop;                    // Pobrany wierzchołek usuwamy ze stosu
      VS[u] := false;           // Zapamiętujemy, że nie ma go już na stosie
      C[u] := v;                // Zapamiętujemy numer silnie spójnej składowej
    until u = v;                // Kontynuujemy aż do korzenia składowej
  end;
end;

// Funkcja bada istnienie cyklu lub ścieżki Eulera
// Zwraca:
// 0 - brak cyklu i ścieżki
// 1 - jest ścieżka Eulera
// 2 - jest cykl Eulera
//------------------------------------------------
function isEulerian : integer;
var
  v,cinout,coutin : integer;
begin
  cvn := 0;                  // Zerujemy numer wierzchołka

  for v := 0 to n - 1 do     // Przeglądamy kolejne wierzchołki
    if VN[v] = 0 then DFSscc(v); // W wierzchołku nieodwiedzonym uruchamiamy DFS

  v := 0;                    // Szukamy pierwszego wierzchołka o niezerowym stopniu
  while (v < n) and (Vind[v] + Voutd[v] = 0) do inc(v);
  if v = n then Exit(0);     // Graf jest pusty

  cvn := C[v];               // Zapamiętujemy numer silnie spójnej składowej
  cinout := 0;               // Licznik wierzchołków o większym o 1 stopniu wchodzącym
  coutin := 0;               // Licznik wierzchołków o większym o 1 stopniu wychodzącym

  while v < n do             // Przeglądamy graf
  begin
    if Vind[v] + Voutd[v] > 0 then
    begin
      if C[v] <> cvn then Exit(0); // graf nie jest silnie spójny
      if Vind[v] <> Voutd[v] then
      begin
        if Vind[v] - Voutd[v] = 1 then
        begin
          inc(cinout);
          if cinout > 1 then Exit(0); // Za dużo wierzchołków o nierównych stopniach
        end
        else if Voutd[v] - Vind[v] = 1 then
        begin
          inc(coutin);
          if coutin > 1 then Exit(0); // Za dużo wierzchołków o nierównych stopniach
        end
        else Exit(0); // Stopnie różnią się o więcej niż 1
      end;
    end;
    inc(v);
  end;

  // Analizujemy stan liczników

  if cinout = 1 then Exit(1) // mamy ścieżkę Eulera
  else               Exit(2) // mamy cykl Eulera
end;

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

var
  i,v,u      : integer;
  p,r        : PslistEl;

begin
  S.init;                           // Tworzymy pusty stos

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

  SetLength(graf,n);                // Tworzymy tablice dynamiczne
  SetLength(VN,n);
  SetLength(VS,n);
  SetLength(VLow,n);
  SetLength(Vind,n);
  SetLength(Voutd,n);
  SetLength(C,n);

  // Inicjujemy tablice

  for i := 0 to n - 1 do
  begin
    graf[i]  := nil;
    VN[i]    := 0;
    Vind[i]  := 0;
    Voutd[i] := 0;
    VS[i]    := false;
  end;

  // Odczytujemy kolejne definicje krawędzi.

  for i := 0 to m - 1 do
  begin
    read(v,u);               // Wierzchołki tworzące krawędź
    new(p);                  // Tworzymy nowy element
    p^.v := u;               // Numerujemy go jako u
    p^.next := graf[v];      // i dodajemy na początek listy graf[v]
    graf[v] := p;
  end;

  writeln;

  // Badamy graf

  case isEulerian of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;

  // Usuwamy zmienne dynamiczne

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

  SetLength(graf,0);
  SetLength(VN,0);
  SetLength(VLow,0);
  SetLength(VS,0);
  SetLength(Vind,0);
  SetLength(Voutd,0);
  SetLength(C,0);
  S.destroy;
end.
Code::Blocks
// Badanie istnienia cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

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

// Definicja typu obiektowego stack
//---------------------------------
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);
};

// Zmienne globalne
//-----------------

int n,m,cvn,*VN,*VLow,*Vind,*Voutd,*C;
bool *VS;
stack S;
slistEl **graf;

//---------------------
// 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;
  }
}

// Procedura wykonująca przejście DFS i wyznaczająca
// silnie spójną składową oraz stopnie wierzchołków
// v - wierzchołek startowy dla DFS
//---------------------------------------------------
void DFSscc(int v)
{
  int u;
  slistEl * p;

  VN[v] = VLow[v] = ++cvn;      // Ustalamy wstępnie parametr Low
  S.push(v);                    // Wierzchołek na stos
  VS[v] = true;                 // Zapamiętujemy, że v jest na stosie

  for(p = graf[v];p;p = p->next) // Przeglądamy listę sąsiadów
  {
    ++Voutd[v];                 // Wyznaczamy stopień wychodzący
    ++Vind[p->v];               // i wchodzący
    if(!VN[p->v])               // Jeśli sąsiad jest nieodwiedzony, to
    {
      DFSscc(p->v);             // wywołujemy dla niego rekurencyjnie DFS
      VLow[v] = min(VLow[v],VLow[p->v]); // i obliczamy parametr Low dla v
    }
    else if(VS[p->v])           // jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] = min(VLow[v],VN[p->v]); // to wyznaczamy parametr Low dla v
  }

  if(VLow[v] == VN[v])          // Sprawdzamy, czy mamy kompletną składową
    do
    {
      u = S.top();              // Pobieramy wierzchołek ze stosu
      S.pop();                  // Pobrany wierzchołek usuwamy ze stosu
      VS[u] = false;            // Zapamiętujemy, że nie ma go już na stosie
      C[u] = v;                 // Zapamiętujemy numer silnie spójnej składowej
    } while(u != v);            // Kontynuujemy aż do korzenia składowej
}

// Funkcja bada istnienie cyklu lub ścieżki Eulera
// Zwraca:
// 0 - brak cyklu i ścieżki
// 1 - jest ścieżka Eulera
// 2 - jest cykl Eulera
//------------------------------------------------
int isEulerian()
{
  int v,cinout,coutin;

  cvn = 0;                  // Zerujemy numer wierzchołka

  for(v = 0; v < n; v++)    // Przeglądamy kolejne wierzchołki
    if(!VN[v]) DFSscc(v);   // W wierzchołku nieodwiedzonym uruchamiamy DFS

  // Szukamy pierwszego wierzchołka o niezerowym stopniu

  for(v = 0; (v < n) && !(Vind[v] + Voutd[v]);v++);

  if(v == n) return 0;      // Graf jest pusty

  cvn = C[v];               // Zapamiętujemy numer silnie spójnej składowej
  cinout = coutin = 0;      // Zerujemy liczniki

  for(;v < n;v++)           // Przeglądamy graf
    if(Vind[v] + Voutd[v])
    {
      if(C[v] != cvn) return 0; // graf nie jest silnie spójny
      if(Vind[v] != Voutd[v])
      {
        if(Vind[v] - Voutd[v] == 1)
        {
          if(++cinout > 1) return 0; // Za dużo wierzchołków o nierównych stopniach
        }
        else if(Voutd[v] - Vind[v] == 1)
        {
          if(++coutin > 1) return 0; // Za dużo wierzchołków o nierównych stopniach
        }
        else return 0;        // Stopnie różnią się o więcej niż 1
      }
    }

  // Analizujemy stan liczników

  if(cinout == 1) return 1; // mamy ścieżkę Eulera
  else            return 2; // mamy cykl Eulera
}

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

int main()
{
  int i,v,u;
  slistEl *p,*r;

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

  graf  = new slistEl * [n];    // Tworzymy tablice dynamiczne
  VN    = new int [n];
  VS    = new bool[n];
  VLow  = new int [n];
  Vind  = new int [n];
  Voutd = new int [n];
  C     = new int [n];

  // Inicjujemy tablice

  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    VN[i]   = Vind[i] = Voutd[i] = 0;
    VS[i]   = false;
  }

  // Odczytujemy kolejne definicje krawędzi.

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;              // Wierzchołki tworzące krawędź
    p = new slistEl;            // Tworzymy nowy element
    p->v = u;                   // Numerujemy go jako u
    p->next = graf[v];          // i dodajemy na początek listy graf[v]
    graf[v] = p;
  }

  cout << endl;

  // Badamy graf

  switch(isEulerian())
  {
    case 0: cout << "NOT AN EULERIAN GRAPH\n"; break;
    case 1: cout << "SEMI-EULERIAN GRAPH\n"; break;
    case 2: cout << "EULERIAN GRAPH\n"; break;
  }

  // Usuwamy zmienne dynamiczne

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

  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;
  delete [] Vind;
  delete [] Voutd;
  delete [] C;

  return 0;
}
Free Basic
' Badanie istnienia cyklu lub ścieżki Eulera
' Data: 3.02.2014
' (C)2014 mgr Jerzy Wałaszek
'-------------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa oraz 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

' Zmienne globalne
'-----------------

Dim Shared As Integer n,m,cvn
Dim Shared As Integer Ptr VN,VLow,Vind,Voutd,C
Dim Shared As Byte Ptr VS
Dim Shared As stack S
Dim Shared As slistEl Ptr Ptr graf

'---------------------
' 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 zwraca mniejszą z liczb a i b
'--------------------------------------
Function min(ByVal a As Integer, ByVal b As Integer) As Integer
  If a < b Then
    Return a
  Else
    Return b
  EndIf
End Function

' Procedura wykonująca przejście DFS i wyznaczająca
' silnie spójną składową oraz stopnie wierzchołków
' v - wierzchołek startowy dla DFS
'---------------------------------------------------
sub DFSscc(ByVal v As Integer)

  Dim As Integer u
  Dim As slistEl Ptr p

  cvn += 1
  VN[v] = cvn
  VLow[v] = cvn                  ' Ustalamy wstępnie parametr Low
  S.push(v)                      ' Wierzchołek na stos
  VS[v] = 1                      ' Zapamiętujemy, że v jest na stosie

  p = graf[v]
  While p                        ' Przeglądamy listę sąsiadów
    Voutd[v] += 1                ' Wyznaczamy stopień wychodzący
    Vind[p->v] += 1              ' i wchodzący
    If VN[p->v] = 0 Then         ' Jeśli sąsiad jest nieodwiedzony, to
      DFSscc(p->v)               ' wywołujemy dla niego rekurencyjnie DFS
      VLow[v] = min(VLow[v],VLow[p->v]) ' i obliczamy parametr Low dla v
    ElseIf VS[p->v] = 1 Then     ' jeśli sąsiad odwiedzony, lecz wciąż na stosie,
      VLow[v] = min(VLow[v],VN[p->v]) ' to wyznaczamy parametr Low dla v
    End If
    p = p->Next
  Wend

  If VLow[v] = VN[v] Then        ' Sprawdzamy, czy mamy kompletną składową
    Do
      u = S.top()                ' Pobieramy wierzchołek ze stosu
      S.pop()                    ' Pobrany wierzchołek usuwamy ze stosu
      VS[u] = 0                  ' Zapamiętujemy, że nie ma go już na stosie
      C[u] = v                   ' Zapamiętujemy numer silnie spójnej składowej
    Loop While u <> v            ' Kontynuujemy aż do korzenia składowej
  End If
End Sub

' Funkcja bada istnienie cyklu lub ścieżki Eulera
' Zwraca:
' 0 - brak cyklu i ścieżki
' 1 - jest ścieżka Eulera
' 2 - jest cykl Eulera
'------------------------------------------------
Function isEulerian() As Integer

  Dim As Integer v,cinout,coutin

  cvn = 0                        ' Zerujemy numer wierzchołka

  For v = 0 To n - 1             ' Przeglądamy kolejne wierzchołki
    If VN[v] = 0 then DFSscc(v)  ' W wierzchołku nieodwiedzonym uruchamiamy DFS
  Next
  
  ' Szukamy pierwszego wierzchołka o niezerowym stopniu

  v = 0
  While (v < n) AndAlso (Vind[v] + Voutd[v] = 0)
    v += 1
  Wend

  If v = n then Return 0         ' Graf jest pusty

  cvn = C[v]                     ' Zapamiętujemy numer silnie spójnej składowej
  cinout = 0                     ' Zerujemy liczniki
  coutin = 0
  
  While v < n                    ' Przeglądamy graf
    If Vind[v] + Voutd[v] > 0 Then
      If C[v] <> cvn Then Return 0 ' graf nie jest silnie spójny
      If Vind[v] <> Voutd[v] Then
        If Vind[v] - Voutd[v] = 1 Then
          cinout += 1
          If cinout > 1 then return 0 ' Za dużo wierzchołków o nierównych stopniach
        ElseIf Voutd[v] - Vind[v] = 1 Then
          coutin += 1
          If coutin > 1 Then Return 0 ' Za dużo wierzchołków o nierównych stopniach
        Else
          Return 0               ' Stopnie różnią się o więcej niż 1
        End If 
      End If
    End If
    v += 1
  Wend
  
  ' Analizujemy stan liczników

  If cinout = 1 Then Return 1    ' mamy ścieżkę Eulera
  return 2                       ' mamy cykl Eulera
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer i,v,u
Dim As slistEl Ptr p,r

Open Cons For Input As #1

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

graf  = New slistEl Ptr [n]      ' Tworzymy tablice dynamiczne
VN    = New Integer [n]
VS    = New Byte    [n]
VLow  = New Integer [n]
Vind  = New Integer [n]
Voutd = New Integer [n]
C     = New Integer [n]

' Inicjujemy tablice

For i = 0 To n - 1
  graf[i]  = 0
  VN[i]    = 0
  Vind[i]  = 0
  Voutd[i] = 0
  VS[i]    = 0
Next

' Odczytujemy kolejne definicje krawędzi.

For i = 1 To m
  Input #1,v,u                   ' Wierzchołki tworzące krawędź
  p = New slistEl                ' Tworzymy nowy element
  p->v = u                       ' Numerujemy go jako w
  p->next = graf[v]              ' Dodajemy go na początek listy A[v]
  graf[v] = p
Next

Close #1

Print

' Badamy graf

Select Case isEulerian()
  Case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2 
    Print "EULERIAN GRAPH"
End Select

' Usuwamy tablice dynamiczne

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

Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS
Delete [] Vind
Delete [] Voutd
Delete [] C

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

EULERIAN GRAPH
9 17
0 1 0 7
1 2 1 5
2 3 2 4
3 0 3 7
4 5 4 8
5 2 5 7
6 3
7 4 7 6 7 8
8 1

SEMI-EULERIAN GRAPH
9 10
0 4
1 5 1 6
2 7
3 1
4 2
5 8
6 3
7 0
8 1

NOT AN EULERIAN 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.