Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Znajdowanie cyklu lub ścieżki Hamiltona

SPIS TREŚCI

Problem

W danym grafie należy znaleźć cykl lub ścieżkę Hamiltona, jeśli istnieją.

Rozwiązanie

obrazek

obrazek

Cykl Hamiltona:
A B H I Q P G F O T S R K J C D L M N E A

Ścieżka Hamiltona (ang. Hamiltonian path) jest taką ścieżką w grafie, która odwiedza każdy jego wierzchołek dokładnie jeden raz.

Cykl Hamiltona (ang. Hamiltonian cycle) jest cyklem, który odwiedza każdy wierzchołek grafu dokładnie jeden raz (za wyjątkiem pierwszego, od którego cykl się zaczyna i w którym się kończy ).

Graf zawierający ścieżkę lub cykl Hamiltona nazywamy grafem hamiltonowskim (ang. Hamiltonian graph ).

Chociaż brzmi to dosyć prosto, to jednak znalezienie cyklu lub ścieżki Hamiltona w grafie jest bardzo trudne obliczeniowo. Problem ten zalicza się to tzw. problemów NP zupełnych, co oznacza, że dla dużej liczby wierzchołków jest on praktycznie nierozwiązywalny w sensownym czasie (o ile nie masz do dyspozycji całych milionów, miliardów lub więcej lat ). Jeśli udałoby ci się rozwiązać znajdowanie cykli lub ścieżek Hamiltona w czasie wielomianowym, to prawdopodobnie otrzymałbyś Nagrodę Nobla z matematyki. Rozwiązania takiego wciąż brak i prawdopodobnie nie istnieje.

Aby graf mógł posiadać cykl Hamiltona, musi być spójny – jest to oczywiste. W grafie niespójnym istnieją wierzchołki, pomiędzy którymi brak ścieżki, zatem nie można ich odwiedzić.

Można podać prosty algorytm rekurencyjny znajdowania wszystkich cykli i ścieżek Hamiltona, jednakże posiada on złożoność O ( n! ), co czyni go zupełnie niepraktycznym dla większych grafów (zawierających powyżej 30 wierzchołków ). Jednakże dla tych małych można go stosować w celach dydaktycznych. Zasada działania naszego algorytmu jest następująca:

Za pomocą odpowiednio zmodyfikowanej procedury DFS przeglądamy graf począwszy od wierzchołka nr 0 (wybór wierzchołka nie ma znaczenia, ponieważ możliwa ścieżka lub cykl Hamiltona musi przechodzić przez wszystkie wierzchołki grafu ). Przetwarzany wierzchołek umieszczamy na stosie. Następnie sprawdzamy, czy stos zawiera n wierzchołków. Jeśli tak, to otrzymaliśmy ścieżkę Hamiltona. W takim przypadku sprawdzamy, czy ostatni wierzchołek ścieżki jest połączony krawędzią z wierzchołkiem nr 0. Jeśli tak, to ścieżka tworzy cykl Hamiltona - wyprowadzamy jej zawartość ze stosu (dla cyklu dodatkowo dodajemy na końcu wierzchołek 0  ), usuwamy ostatni wierzchołek ze stosu i wycofujemy się na wyższy poziom rekurencji, gdzie będą rozważone inne ścieżki lub cykle Hamiltona.

Jeśli stos nie zawiera n wierzchołków, to rekurencyjnie wywołujemy procedurę DFS dla wszystkich nieodwiedzonych sąsiadów. Wierzchołek usuwamy ze stosu i kasujemy informację o jego odwiedzeniu, po czym wycofujemy się na wyższy poziom rekurencji.

Powyższy algorytm produkuje ścieżki i cykle Hamiltona w kierunku odwrotnym do ich przebywania przez DFS. Dla grafu nieskierowanego nie ma to znaczenia. W grafie skierowanym należy tę kolejność odwrócić. Stos można w prosty sposób zrealizować w dynamicznej tablicy n  elementowej. Wtedy bez problemu da się odczytywać wierzchołki cyklu w kolejności ich przebywania.

Algorytm wyszukiwania ścieżek i cykli Hamiltona

Funkcja rekurencyjna DFSHamilton ( n, graf, v, visited, S )

Wejście:

n  –  liczba wierzchołków w grafie, n   ∈ C.
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v  –  bieżący wierzchołek grafu, v   ∈ C.
visited  –  n elementowa tablica odwiedzin.
S  –  stos wierzchołków.

Wyjście:

Wszystkie cykle i ścieżki Hamiltona w grafie.
Zmienne pomocnicze:
test  –  zmienna logiczna do testowania cyklu lub ścieżki Hamiltona.
u  –  wierzchołek grafu, u  ∈ C.

Lista kroków:

K01: S.push ( v  ) umieszczamy v na stosie
K02: Jeśli S  zawiera mniej niż n  wierzchołków,
to idź do kroku K10
mamy ścieżkę Hamiltona?
K03: test  ← false zakładamy brak cyklu Hamiltona
K04: Dla każdego sąsiada u  wierzchołka v :
wykonuj
krok K05
przeglądamy sąsiadów v
K05:     Jeśli u  = 0,
    to test  ← true
    i idź do kroku K06
 
K06: Jeśli test  = true,
to pisz "Hamiltonian Cycle :"
inaczej pisz "Hamiltonian Path : "
 
K07: Pisz zawartość S  bez usuwania danych z S  
K08: Jeśli test  = true,
to pisz 0
dla cyklu dopisujemy wierzchołek startowy
K09: Idź do kroku K14  
K10: visited [ v ] ← true oznaczamy wierzchołek jako odwiedzony
K11: Dla każdego sąsiada u  wierzchołka v :
wykonuj
krok K12
przeglądamy sąsiadów wierzchołka v
K12:     Jeśli visited [ u  ] = false,
    to DFSHamilton ( n, graf, u, visited, S  )
dla sąsiadów nieodwiedzonych wykonujemy wywołanie rekurencyjne
K13: visited [ v  ] ← false wycofujemy się z wierzchołka v
K14: S.pop( ) wierzchołek v usuwamy ze stosu
K15: Zakończ  

Funkcję należy wywołać z pustym stosem S  i wyzerowaną tablicą visited  jako DFSHamilton ( n, graf, 0, visited, S ).


Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu nieskierowanego i wyszukuje w nim wszystkie cykle oraz ścieżki Hamiltona. Wyniki są odpowiednio wyświetlane w oknie konsoli.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
Graf z cyklami i ścieżkami Hamiltona
obrazek
8 13
0 1 0 3 0 4
1 2 1 4 1 5
2 3 2 6
3 5 3 6
4 7
5 7
6 7
Pascal
// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

program hamilton;

// Typy danych

type
  PslistEl = ^slistEl;          // Wskaźnik elementów listy
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

// Zmienne globalne

var
  m, n  : integer;              // Liczba krawędzi i wierzchołków
  graf : array of PslistEl;     // Tablica list sąsiedztwa
  S    : array of integer;      // Tablica-stos
  sptr : integer;               // Wskaźnik stosu
  visited : array of boolean;   // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v - wierzchołek bieżący
//--------------------------------------------------------------
procedure DFSHamilton ( v : integer );
var
  i    : integer;
  test : boolean;
  p    : PslistEl;
begin
  S [ sptr ] := v;              // Wierzchołek v na stos
  inc ( sptr );
  if sptr < n then              // Jest ścieżka Hamiltona?
  begin
    visited [ v ] := true;      // Nie ma, odwiedzamy v
    p := graf [ v ];
    while p <> nil do           // Przeglądamy sąsiadów v
    begin
      if not visited [ p^.v ] then DFSHamilton ( p^.v ); // Wywołanie rekurencyjne
      p := p^.next;             // Następny sąsiad
    end;
    visited [ v ] := false;     // Wycofujemy się z v
  end
  else                          // Jest ścieżka Hamiltona
  begin
    test := false;              // Zakładamy brak cyklu
    p := graf [ v ];               // Przeglądamy sąsiadów
    while p <> nil do
    begin
      if p^.v = 0 then          // Jeśli sąsiadem jest wierzchołek 0, 
      begin
        test := true;           // to mamy cykl
        break;
      end;
      p := p^.next;             // Następny sąsiad
    end;
    if test then write ( 'Hamiltonian Cycle :' )
    else         write ( 'Hamiltonian Path  :' );
    for i := 0 to sptr - 1 do   // Wypisujemy ścieżkę Hamiltona
      write ( S [ i ] :3 );
    if test then write ( 0:3 ); // Dla cyklu dopisujemy wierzchołek startowy
    writeln;
  end;
  dec ( sptr );                 // Wierzchołek v usuwamy ze stosu
end;

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

var
  i, v1, v2 : integer;
  p, r     : PslistEl;
begin
  read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength ( graf, n );
  SetLength ( visited, n );
  for i := 0 to n - 1 do
  begin
    graf [ i ]    := nil;
    visited [ i ] := false;
  end;
  SetLength ( S, n );
  sptr := 0;

  // Odczytujemy definicje krawędzi grafu

  for i := 0 to m - 1 do
  begin
    read ( v1, v2 );
    new ( p );
    p^.v := v2;
    p^.next := graf [ v1 ];
    graf [ v1 ] := p;
    new ( p );
    p^.v := v1;
    p^.next := graf [ v2 ];
    graf [ v2 ] := p;
  end;

  writeln;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton ( 0 );

  // Usuwamy zmienne dynamiczne

  SetLength ( visited, 0 );
  SetLength ( S, 0 );

  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 );
end.
C++
// Wyszukiwanie cykli i ścieżek Hamiltona
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

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

// Zmienne globalne

int m, n;                       // Liczba krawędzi i wierzchołków
slistEl **graf;                 // Tablica list sąsiedztwa
int *S;                         // Tablica-stos
int sptr;                       // Wskaźnik stosu
bool *visited;                  // Tablica odwiedzin

// Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
// v - wierzchołek bieżący
//--------------------------------------------------------------
void DFSHamilton ( int v )
{
  int i;
  bool test;
  slistEl *p;

  S [ sptr++ ] = v;             // Wierzchołek v na stos
  if( sptr < n )                // Jest ścieżka Hamiltona?
  {
    visited [ v ] = true;       // Nie ma, odwiedzamy v
    for( p = graf [ v ]; p; p = p->next ) // Przeglądamy sąsiadów v
      if( !visited [ p->v ] ) DFSHamilton ( p->v ); // Wywołanie rekurencyjne
    visited [ v ] = false;      // Wycofujemy się z v
  }
  else                          // Jest ścieżka Hamiltona
  {
    test = false;               // Zakładamy brak cyklu
    for( p = graf [ v ]; p; p = p->next ) // Przeglądamy sąsiadów
      if( ! ( p->v ) )          // Jeśli sąsiadem jest wierzchołek 0, 
      {
        test = true;            // to mamy cykl
        break;
      }

    if( test ) cout << "Hamiltonian Cycle :";
    else     cout << "Hamiltonian Path  :";

    for( i = 0; i < sptr; i++ ) // Wypisujemy ścieżkę Hamiltona
      cout << setw ( 3 ) << S [ i ];
    if( test ) cout << setw ( 3 ) << 0; // Dla cyklu dopisujemy wierzchołek startowy
    cout << endl;
  }
  sptr--;                       // Wierzchołek v usuwamy ze stosu
}

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

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

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

  // Tworzymy tablice dynamiczne

  graf    = new slistEl * [ n ];
  visited = new bool [ n ];
  for( i = 0; i < n; i++ )
  {
    graf [ i ]    = NULL;
    visited [ i ] = false;
  }
  S = new int [ n ];
  sptr = 0;

  // Odczytujemy definicje krawędzi grafu

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;
    p = new slistEl;
    p->v = v2;
    p->next = graf [ v1 ];
    graf [ v1 ] = p;
    p = new slistEl;
    p->v = v1;
    p->next = graf [ v2 ];
    graf [ v2 ] = p;
  }

  cout << endl;

  // Wyświetlamy ścieżki i cykle Hamiltona

  DFSHamilton ( 0 );

  // Usuwamy zmienne dynamiczne

  delete [ ] visited;
  delete [ ] S;

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

  delete [ ] graf;

  return 0;
}
Basic
' Wyszukiwanie cykli i ścieżek Hamiltona
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------------------

' Typy danych

Type slistEl
  Next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer m, n     ' Liczba krawędzi i wierzchołków
Dim Shared As slistEl Ptr Ptr graf ' Tablica list sąsiedztwa
Dim Shared As Integer Ptr S    ' Tablica-stos
Dim Shared As Integer sptr     ' Wskaźnik stosu
Dim Shared As Byte Ptr visited ' Tablica odwiedzin

' Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
' v - wierzchołek bieżący
'--------------------------------------------------------------
Sub DFSHamilton ( ByVal v As Integer )

  Dim As Integer i, test
  Dim As slistEl Ptr p

  S [ sptr ] = v          ' Wierzchołek v na stos
  sptr += 1
  If sptr < n Then        ' Jest ścieżka Hamiltona?
    visited [ v ] = 1     ' Nie ma, odwiedzamy v
    p = graf [ v ] 
    While p               ' Przeglądamy sąsiadów v
      If visited [ p->v ] = 0 Then DFSHamilton ( p->v ) ' Wywołanie rekurencyjne
      p = p->Next         ' Następny sąsiad
    Wend
    visited [ v ] = 0     ' Wycofujemy się z v
  Else                    ' Jest ścieżka Hamiltona
    test = 0              ' Zakładamy brak cyklu
    p = graf [ v ] 
    While p               ' Przeglądamy sąsiadów
      If p->v = 0 Then    ' Jeśli sąsiadem jest wierzchołek 0, 
        test = 1          ' to mamy cykl
        Exit While
      End If
      p = p->Next         ' Następny sąsiad
    Wend
    
    If test = 1 then
    	Print "Hamiltonian Cycle :";
    Else
      Print "Hamiltonian Path  :";
    End If
    
    For i = 0 To sptr - 1 ' Wypisujemy ścieżkę Hamiltona
      Print Using "###";S [ i ];
    Next
    
    If test = 1 Then Print Using "###";0; ' Dla cyklu dopisujemy wierzchołek startowy
    Print
  End if
  sptr -= 1               ' Wierzchołek v usuwamy ze stosu
End Sub

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

Dim As Integer i, v1, v2
Dim As slistEl Ptr p, r

Open Cons For Input As #1

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

' Tworzymy tablice dynamiczne

graf    = New slistEl Ptr [ n ] 
visited = New Byte [ n ] 
For i = 0 To n - 1
  graf [ i ]    = 0
  visited [ i ] = 0
Next
S = New Integer [ n ] 
sptr = 0

' Odczytujemy definicje krawędzi grafu

For i = 0 To m - 1
  Input #1, v1, v2
  p = New slistEl
  p->v = v2
  p->next = graf [ v1 ] 
  graf [ v1 ] = p
  p = New slistEl
  p->v = v1
  p->next = graf [ v2 ] 
  graf [ v2 ] = p
Next

Print

' Wyświetlamy ścieżki i cykle Hamiltona

DFSHamilton ( 0 )

' Usuwamy zmienne dynamiczne

Delete [ ] visited
Delete [ ] S

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

Delete [ ] graf

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

Hamiltonian Path :  0  4  7  6  3  5  1  2
Hamiltonian Path :  0  4  7  6  3  2  1  5
Hamiltonian Cycle :  0  4  7  6  2  3  5  1  0
Hamiltonian Cycle :  0  4  7  6  2  1  5  3  0
Hamiltonian Cycle :  0  4  7  5  3  6  2  1  0
Hamiltonian Cycle :  0  4  7  5  1  2  6  3  0
Hamiltonian Path :  0  4  7  5  1  2  3  6
Hamiltonian Path :  0  4  1  5  7  6  3  2
Hamiltonian Cycle :  0  4  1  5  7  6  2  3  0
Hamiltonian Path :  0  4  1  5  3  2  6  7
Hamiltonian Cycle :  0  4  1  2  6  7  5  3  0
Hamiltonian Path :  0  4  1  2  6  3  5  7
Hamiltonian Path :  0  4  1  2  3  6  7  5
Hamiltonian Path :  0  4  1  2  3  5  7  6
Hamiltonian Cycle :  0  3  6  2  1  5  7  4  0
Hamiltonian Path :  0  3  6  2  1  4  7  5
Hamiltonian Cycle :  0  3  5  7  6  2  1  4  0
Hamiltonian Path :  0  3  5  7  4  1  2  6
Hamiltonian Path :  0  3  5  1  4  7  6  2
Hamiltonian Cycle :  0  3  5  1  2  6  7  4  0
Hamiltonian Cycle :  0  3  2  6  7  5  1  4  0
Hamiltonian Path :  0  3  2  6  7  4  1  5
Hamiltonian Cycle :  0  1  5  3  2  6  7  4  0
Hamiltonian Path :  0  1  4  7  6  2  3  5
Hamiltonian Path :  0  1  4  7  5  3  6  2
Hamiltonian Path :  0  1  4  7  5  3  2  6
Hamiltonian Cycle :  0  1  2  6  3  5  7  4  0

Zadania dla ambitnych

Zwróć uwagę, że dla grafu nieskierowanego liczba cykli Hamiltona jest zawsze parzysta. Połowa z nich to te same cykle, lecz przebywanie w odwrotnym kierunku. Np:
0  4  7  6  2  3  5  1  0
0  1  5  3  2  6  7  4  0

W grafie nieskierowanym cykle takie są traktowane jako ten sam cykl Hamiltona. Zatem w naszym przykładowym grafie jest tylko 6 różnych cykli Hamiltona. Zastanów się, czy można tak zmodyfikować nasz algorytm, aby nie pokazywał cykli lustrzanych.

Zastanów się, jak zmodyfikować algorytm, aby wyszukiwał tylko pierwszy cykl Hamiltona.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

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

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

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

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

Informacje dodatkowe.