Algorytmy i Struktury Danych - Znajdowanie cyklu lub ścieżki Hamiltona

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 DFSH(n,graf,v,vs,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.
vs : n elementowa tablica odwiedzin.
S : stos wierzchołków.

Wyjście:

Wszystkie cykle i ścieżki Hamiltona w grafie.

Elementy 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: ; mamy ścieżkę Hamiltona?
     Jeśli S zawiera mniej niż n wierzchołków,
     to idź do kroku K10
K03: test ← false ; zakładamy brak cyklu Hamiltona
K04: Dla każdego sąsiada u wierzchołka v: ; przeglądamy sąsiadów v
     wykonuj krok K05
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,  ; dla cyklu dopisujemy wierzchołek startowy
     to pisz 0
K09: Idź do kroku K14
K10: vs[v] ← true ; oznaczamy wierzchołek jako odwiedzony
K11: Dla każdego sąsiada u wierzchołka v: ; przeglądamy
     wykonuj krok K12 ; sąsiadów wierzchołka v
K12:   Jeśli vs[u] = false, ; dla sąsiadów nieodwiedzonych
       to DFSH(n,graf,u,vs,S) ; wykonujemy wywołanie rekurencyjne
K13: vs[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ą vs jako DFSH(n,graf,0,vs,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
  // Wskaźnik elementów listy
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    v    : integer;
  end;

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

// Rekurencyjna procedura
// wyznaczająca ścieżki
// i cykle Hamiltona
// v - wierzchołek bieżący
//------------------------
procedure DFSH(v : integer);
var
  i : integer;
  test : boolean;
  p : PSLel;

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

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

var
  i, v1, v2 : integer;
  p, r : PSLel;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(vs, n);
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    vs[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
  DFSH(0);
  // Usuwamy zmienne dynamiczne
  SetLength(vs, 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 SLel
{
  SLel * next;
  int v;
};

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

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

  // Wierzchołek v na stos
  S[sptr++] = v;
  // Jest ścieżka Hamiltona?
  if(sptr < n)
  {
    // Nie ma, odwiedzamy v
    vs[v] = true;
    // Przeglądamy sąsiadów v
    for(p = graf[v]; p; p = p->next)
      // Wywołanie rekurencyjne
      if(!vs [p->v]) DFSH(p->v);
    // Wycofujemy się z v
    vs[v] = false;
  }
  // Jest ścieżka Hamiltona
  else
  {
    // Zakładamy brak cyklu
    test = false;
    // Przeglądamy sąsiadów
    for(p = graf[v]; p; p = p->next)
      // Jeśli sąsiadem jest
      // wierzchołek 0,
      if(!(p->v))
      {
        // to mamy cykl
        test = true;
        break;
      }
    if(test)
      cout << "Hamiltonian Cycle :";
    else
      cout << "Hamiltonian Path  :";
    // Wypisujemy ścieżkę Hamiltona
    for(i = 0; i < sptr; i++)
      cout << setw(3) << S[i];
    if(test)
      // Dla cyklu dopisujemy
      // wierzchołek startowy
      cout << setw(3) << 0;
    cout << endl;
  }
  // Wierzchołek v usuwamy
  // ze stosu
  sptr--;
}

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new SLel * [n];
  vs = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    vs[i] = false;
  }
  S = new int [n];
  sptr = 0;
  // Odczytujemy definicje
  // krawędzi grafu
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    p = new SLel;
    p->v = v2;
    p->next = graf[v1];
    graf[v1] = p;
    p = new SLel;
    p->v = v1;
    p->next = graf[v2];
    graf[v2] = p;
  }
  cout << endl;
  // Wyświetlamy ścieżki
  // i cykle Hamiltona
  DFSH(0);
  // Usuwamy zmienne dynamiczne
  delete [] vs;
  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 SLel
  Next As SLel Ptr
  v As Integer
End Type

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

' Rekurencyjna procedura wyznaczająca
' ścieżki i cykle Hamiltona
' v - wierzchołek bieżący
'------------------------------------
Sub DFSH(ByVal v As Integer)
  Dim As Integer i, test
  Dim As SLel Ptr p

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

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

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

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf    = New SLel Ptr [n]
vs = New Byte [n]
For i = 0 To n-1
  graf[i] = 0
  vs[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 SLel
  p->v = v2
  p->next = graf[v1]
  graf[v1] = p
  p = New SLel
  p->v = v1
  p->next = graf[v2]
  graf[v2] = p
Next
Print
' Wyświetlamy ścieżki i cykle Hamiltona
DFSH(0)
' Usuwamy zmienne dynamiczne
Delete [] vs
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

Python (dodatek)

# Wyszukiwanie cykli
# i ścieżek Hamiltona
# Data: 11.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klsasa listy
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Rekurencyjna procedura wyznaczająca
# ścieżki i cykle Hamiltona
# v - wierzchołek bieżący
#------------------------------------
def dfs_h(v):
    global s,sptr,vs,graf,n

    # Wierzchołek v na stos
    s[sptr] = v
    sptr += 1
    # Jest ścieżka Hamiltona?
    if sptr < n:
        # Nie ma, odwiedzamy v
        vs[v] = True
        p = graf[v]
        # Przeglądamy sąsiadów v
        while p:
            if not vs[p.v]:
                # Wywołanie rekurencyjne
                dfs_h(p.v)
            # Następny sąsiad
            p = p.next
        # Wycofujemy się z v
        vs[v] = False
    # Jest ścieżka Hamiltona
    else:
        # Zakładamy brak cyklu
        test = False
        p = graf[v]
        # Przeglądamy sąsiadów
        while p:
            # Jeśli sąsiadem jest
            # wierzchołek 0, 
            if not p.v:
                # to mamy cykl
                test = True
                break
            # Następny sąsiad
            p = p.next
        if test:
            print("Hamiltonian Cycle :",end="")
        else:
            print("Hamiltonian Path  :",end="")
        # Wypisujemy ścieżkę Hamiltona
        for i in range(sptr):
            print("%3d" % s[i],end="")
        if test:
            # Dla cyklu dopisujemy
            # wierzchołek startowy
            print("  0",end="")
        print()
    # Wierzchołek v usuwamy ze stosu
    sptr -= 1


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
vs = [False] * n
s = [0] * n
sptr = 0
# Odczytujemy definicje krawędzi grafu
for i in range(m):
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    p = SLel()
    p.v = v2
    p.next = graf[v1]
    graf[v1] = p
    p = SLel()
    p.v = v1
    p.next = graf[v2]
    graf[v2] = p
print()
# Wyświetlamy ścieżki i cykle Hamiltona
dfs_h(0)
# Usuwamy zmienne dynamiczne
del vs,s
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf

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.

do podrozdziału do strony

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.

Znajdowanie cyklu lub ścieżki Hamiltona

Problem

Rozwiązanie