logo

TechCodeview

Ciclo Hamiltoniano

Cos'è il ciclo hamiltoniano?

Ciclo o circuito hamiltoniano in un grafico G è un ciclo che visita ogni vertice di G esattamente una volta e ritorna al vertice di partenza.

  • Se il grafico contiene un ciclo hamiltoniano, viene chiamato Grafico hamiltoniano altrimenti lo è non hamiltoniano .
  • Trovare un ciclo hamiltoniano in un grafico è un'operazione ben nota Problema NP-completo , il che significa che non esiste un algoritmo efficiente noto per risolverlo per tutti i tipi di grafici. Tuttavia, può essere risolto per tipi di grafici piccoli o specifici.
    Il problema del ciclo hamiltoniano ha applicazioni pratiche in vari campi, come ad esempio logistica, progettazione di reti e informatica .

Cos'è il percorso hamiltoniano?

Percorso hamiltoniano in un grafico G è un cammino che visita ogni vertice di G esattamente una volta e Percorso hamiltoniano non deve ritornare al vertice iniziale. È un percorso aperto.



  • Simile al Ciclo Hamiltoniano problema, trovare a Percorso hamiltoniano in un grafico generale è anche NP-completo e può essere impegnativo. Tuttavia, spesso è un problema più semplice che trovare un ciclo hamiltoniano.
  • I percorsi hamiltoniani hanno applicazioni in vari campi, come ad esempio trovare percorsi ottimali nelle reti di trasporto, nella progettazione di circuiti e nella ricerca sulla teoria dei grafi .

Dichiarazione dei problemi: Dato un grafo non orientato, il compito è determinare se il grafo contiene o meno un ciclo hamiltoniano. Se contiene, stampa il percorso.

Esempio:

Ingresso: grafico[][] = {{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 1},{0, 1, 1, 1, 0}}



Grafico di input[][]

decodifica js base64

Produzione: {0, 1, 2, 4, 3, 0}.

Ingresso: grafico[][] = {{0, 1, 0, 1, 0},{1, 0, 1, 1, 1},{0, 1, 0, 0, 1},{1, 1, 0, 0, 0},{0, 1, 1, 0, 0}}



one_img2

Grafico di input[][]

Produzione: La soluzione non esiste
Consigliato: risolverlo PRATICA innanzitutto, prima di passare alla soluzione.

Algoritmo ingenuo : Questo problema può essere risolto utilizzando l'idea seguente:

Genera tutte le possibili configurazioni di vertici e stampa una configurazione che soddisfi i vincoli specificati. Ci saranno n! (n fattoriali) configurazioni. Quindi la complessità temporale complessiva di questo approccio sarà SU!).

Utilizzo del ciclo hamiltoniano Algoritmo di backtracking :

Crea un array di percorsi vuoto e aggiungi il vertice 0 ad esso. Aggiungi altri vertici, iniziando dal vertice 1 . Prima di aggiungere un vertice, controlla se è adiacente al vertice aggiunto in precedenza e non è già aggiunto. Se troviamo un vertice di questo tipo, aggiungiamo il vertice come parte della soluzione. Se non troviamo un vertice allora torniamo falso .

Illustrazioni:

Scopriamo il ciclo hamiltoniano per il grafico seguente:

Senza titolo-Diagra-(1)
  • Inizia con il nodo 0 .
  • Applicare DFS per trovare il percorso hamiltoniano.
  • Quando il caso base viene raggiunto (ad es. numero totale di nodi attraversati == V (vertice totale) ):
    • Controlla se il nodo corrente è vicino al nodo iniziale.
    • Come nodo 2 e nodo 0 non sono vicini l'uno dell'altro, quindi ritornate da esso.
Ciclo hamiltoniano

A partire dal nodo iniziale 0 che chiama DFS

  • Poiché il ciclo non si trova nel percorso {0, 3, 1, 4, 2}. Quindi, ritorna dal nodo 2, nodo 4.
file
  • Ora, esplora un'altra opzione per il nodo 1 (ovvero il nodo 2)
  • Quando raggiunge nuovamente la condizione di base, controlla il ciclo hamiltoniano
  • Poiché il nodo 4 non è vicino al nodo 0, ancora una volta il ciclo non viene trovato, quindi ritorna.
file
  • Ritorno dal nodo 4, nodo 2, nodo 1.
file
  • Ora esplora altre opzioni per il nodo 3.


hamiltoniano-1

Ciclo Hamiltoniano

  • Nel cammino hamiltoniano {0,3,4,2,1,0} otteniamo il ciclo poiché il nodo 1 è il vicino del nodo 0.
  • Quindi stampa questo percorso ciclico.
  • Questo è il nostro ciclo hamiltoniano.

Di seguito è riportata l'implementazione del Backtracking per trovare il ciclo hamiltoniano:

C++ 
/* C++ program for solution of Hamiltonian  Cycle problem using backtracking */ #include  using namespace std; // Number of vertices in the graph  #define V 5  void printSolution(int path[]);  /* A utility function to check if  the vertex v can be added at index 'pos'  in the Hamiltonian Cycle constructed  so far (stored in 'path[]') */ bool isSafe(int v, bool graph[V][V],   int path[], int pos)  {   /* Check if this vertex is an adjacent   vertex of the previously added vertex. */  if (graph [path[pos - 1]][ v ] == 0)   return false;   /* Check if the vertex has already been included.   This step can be optimized by creating  an array of size V */  for (int i = 0; i < pos; i++)   if (path[i] == v)   return false;   return true;  }  /* A recursive utility function  to solve hamiltonian cycle problem */ bool hamCycleUtil(bool graph[V][V],   int path[], int pos)  {   /* base case: If all vertices are   included in Hamiltonian Cycle */  if (pos == V)   {   // And if there is an edge from the   // last included vertex to the first vertex   if (graph[path[pos - 1]][path[0]] == 1)   return true;   else  return false;   }   // Try different vertices as a next candidate   // in Hamiltonian Cycle. We don't try for 0 as   // we included 0 as starting point in hamCycle()   for (int v = 1; v < V; v++)   {   /* Check if this vertex can be added   // to Hamiltonian Cycle */  if (isSafe(v, graph, path, pos))   {   path[pos] = v;   /* recur to construct rest of the path */  if (hamCycleUtil (graph, path, pos + 1) == true)   return true;   /* If adding vertex v doesn't lead to a solution,   then remove it */  path[pos] = -1;   }   }   /* If no vertex can be added to   Hamiltonian Cycle constructed so far,   then return false */  return false;  }  /* This function solves the Hamiltonian Cycle problem  using Backtracking. It mainly uses hamCycleUtil() to  solve the problem. It returns false if there is no  Hamiltonian Cycle possible, otherwise return true  and prints the path. Please note that there may be  more than one solutions, this function prints one  of the feasible solutions. */ bool hamCycle(bool graph[V][V])  {   int *path = new int[V];   for (int i = 0; i < V; i++)   path[i] = -1;   /* Let us put vertex 0 as the first vertex in the path.  If there is a Hamiltonian Cycle, then the path can be   started from any point of the cycle as the graph is undirected */  path[0] = 0;   if (hamCycleUtil(graph, path, 1) == false )   {   cout << '
Solution does not exist';   return false;   }   printSolution(path);   return true;  }  /* A utility function to print solution */ void printSolution(int path[])  {   cout << 'Solution Exists:'  ' Following is one Hamiltonian Cycle 
';   for (int i = 0; i < V; i++)   cout << path[i] << ' ';   // Let us print the first vertex again  // to show the complete cycle   cout << path[0] << ' ';   cout << endl; }  // Driver Code  int main()  {   /* Let us create the following graph   (0)--(1)--(2)   | /  |   | /  |   | /  |   (3)-------(4) */  bool graph1[V][V] = {{0, 1, 0, 1, 0},   {1, 0, 1, 1, 1},   {0, 1, 0, 0, 1},   {1, 1, 0, 0, 1},   {0, 1, 1, 1, 0}};     // Print the solution   hamCycle(graph1);     /* Let us create the following graph   (0)--(1)--(2)   | /  |   | /  |   | /  |   (3) (4) */  bool graph2[V][V] = {{0, 1, 0, 1, 0},   {1, 0, 1, 1, 1},   {0, 1, 0, 0, 1},   {1, 1, 0, 0, 0},   {0, 1, 1, 0, 0}};   // Print the solution   hamCycle(graph2);   return 0;  }  // This is code is contributed by rathbhupendra>
C++ 
#include  using namespace std; int main() {  cout << 'GFG!';  return 0; }>
C 
/* C program for solution of Hamiltonian Cycle problem  using backtracking */ #include // Number of vertices in the graph #define V 5 void printSolution(int path[]); /* A utility function to check if the vertex v can be added at  index 'pos' in the Hamiltonian Cycle constructed so far (stored  in 'path[]') */ int isSafe(int v, int graph[V][V], int path[], int pos) {  /* Check if this vertex is an adjacent vertex of the previously  added vertex. */  if (graph [ path[pos-1] ][ v ] == 0)  return 0;  /* Check if the vertex has already been included.  This step can be optimized by creating an array of size V */  for (int i = 0; i < pos; i++)  if (path[i] == v)  return 0;  return 1; } /* A recursive utility function to solve hamiltonian cycle problem */ int hamCycleUtil(int graph[V][V], int path[], int pos) {  /* base case: If all vertices are included in Hamiltonian Cycle */  if (pos == V)  {  // And if there is an edge from the last included vertex to the  // first vertex  if ( graph[ path[pos-1] ][ path[0] ] == 1 )  return 1;  else  return 0;  }  // Try different vertices as a next candidate in Hamiltonian Cycle.  // We don't try for 0 as we included 0 as starting point in hamCycle()  for (int v = 1; v < V; v++)  {  /* Check if this vertex can be added to Hamiltonian Cycle */  if (isSafe(v, graph, path, pos))  {  path[pos] = v;  /* recur to construct rest of the path */  if (hamCycleUtil (graph, path, pos+1) == 1)  return 1;  /* If adding vertex v doesn't lead to a solution,  then remove it */  path[pos] = -1;  }  }  /* If no vertex can be added to Hamiltonian Cycle constructed so far,  then return false */  return 0; } /* This function solves the Hamiltonian Cycle problem using Backtracking.  It mainly uses hamCycleUtil() to solve the problem. It returns false  if there is no Hamiltonian Cycle possible, otherwise return true and  prints the path. Please note that there may be more than one solutions,  this function prints one of the feasible solutions. */ int hamCycle(int graph[V][V]) {  int path[V];  for (int i = 0; i < V; i++)  path[i] = -1;  /* Let us put vertex 0 as the first vertex in the path. If there is  a Hamiltonian Cycle, then the path can be started from any point  of the cycle as the graph is undirected */  path[0] = 0;  if ( hamCycleUtil(graph, path, 1) == 0 )  {  printf('
Solution does not exist');  return 0;  }  printSolution(path);  return 1; } /* A utility function to print solution */ void printSolution(int path[]) {  printf ('Solution Exists:'  ' Following is one Hamiltonian Cycle 
');  for (int i = 0; i < V; i++)  printf(' %d ', path[i]);  // Let us print the first vertex again to show the complete cycle  printf(' %d ', path[0]);  printf('
'); } // driver program to test above function int main() {  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3)-------(4) */  int graph1[V][V] = {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 1},  {0, 1, 1, 1, 0},  };  // Print the solution  hamCycle(graph1);  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3) (4) */  int graph2[V][V] = {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 0},  {0, 1, 1, 0, 0},  };  // Print the solution  hamCycle(graph2);  return 0; }>
Giava 
/* Java program for solution of Hamiltonian Cycle problem  using backtracking */ class HamiltonianCycle {  final int V = 5;  int path[];  /* A utility function to check if the vertex v can be  added at index 'pos'in the Hamiltonian Cycle  constructed so far (stored in 'path[]') */  boolean isSafe(int v, int graph[][], int path[], int pos)  {  /* Check if this vertex is an adjacent vertex of  the previously added vertex. */  if (graph[path[pos - 1]][v] == 0)  return false;  /* Check if the vertex has already been included.  This step can be optimized by creating an array  of size V */  for (int i = 0; i < pos; i++)  if (path[i] == v)  return false;  return true;  }  /* A recursive utility function to solve hamiltonian  cycle problem */  boolean hamCycleUtil(int graph[][], int path[], int pos)  {  /* base case: If all vertices are included in  Hamiltonian Cycle */  if (pos == V)  {  // And if there is an edge from the last included  // vertex to the first vertex  if (graph[path[pos - 1]][path[0]] == 1)  return true;  else  return false;  }  // Try different vertices as a next candidate in  // Hamiltonian Cycle. We don't try for 0 as we  // included 0 as starting point in hamCycle()  for (int v = 1; v < V; v++)  {  /* Check if this vertex can be added to Hamiltonian  Cycle */  if (isSafe(v, graph, path, pos))  {  path[pos] = v;  /* recur to construct rest of the path */  if (hamCycleUtil(graph, path, pos + 1) == true)  return true;  /* If adding vertex v doesn't lead to a solution,  then remove it */  path[pos] = -1;  }  }  /* If no vertex can be added to Hamiltonian Cycle  constructed so far, then return false */  return false;  }  /* This function solves the Hamiltonian Cycle problem using  Backtracking. It mainly uses hamCycleUtil() to solve the  problem. It returns false if there is no Hamiltonian Cycle  possible, otherwise return true and prints the path.  Please note that there may be more than one solutions,  this function prints one of the feasible solutions. */  int hamCycle(int graph[][])  {  path = new int[V];  for (int i = 0; i < V; i++)  path[i] = -1;  /* Let us put vertex 0 as the first vertex in the path.  If there is a Hamiltonian Cycle, then the path can be  started from any point of the cycle as the graph is  undirected */  path[0] = 0;  if (hamCycleUtil(graph, path, 1) == false)  {  System.out.println('
Solution does not exist');  return 0;  }  printSolution(path);  return 1;  }  /* A utility function to print solution */  void printSolution(int path[])  {  System.out.println('Solution Exists: Following' +  ' is one Hamiltonian Cycle');  for (int i = 0; i < V; i++)  System.out.print(' ' + path[i] + ' ');  // Let us print the first vertex again to show the  // complete cycle  System.out.println(' ' + path[0] + ' ');  }  // driver program to test above function  public static void main(String args[])  {  HamiltonianCycle hamiltonian =  new HamiltonianCycle();  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3)-------(4) */  int graph1[][] = {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 1},  {0, 1, 1, 1, 0},  };  // Print the solution  hamiltonian.hamCycle(graph1);  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3) (4) */  int graph2[][] = {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 0},  {0, 1, 1, 0, 0},  };  // Print the solution  hamiltonian.hamCycle(graph2);  } } // This code is contributed by Abhishek Shankhadhar>
Pitone 
# Python program for solution of  # hamiltonian cycle problem  class Graph(): def __init__(self, vertices): self.graph = [[0 for column in range(vertices)] for row in range(vertices)] self.V = vertices  ''' Check if this vertex is an adjacent vertex   of the previously added vertex and is not   included in the path earlier ''' def isSafe(self, v, pos, path): # Check if current vertex and last vertex  # in path are adjacent  if self.graph[ path[pos-1] ][v] == 0: return False # Check if current vertex not already in path  for vertex in path: if vertex == v: return False return True # A recursive utility function to solve  # hamiltonian cycle problem  def hamCycleUtil(self, path, pos): # base case: if all vertices are  # included in the path  if pos == self.V: # Last vertex must be adjacent to the  # first vertex in path to make a cycle  if self.graph[ path[pos-1] ][ path[0] ] == 1: return True else: return False # Try different vertices as a next candidate  # in Hamiltonian Cycle. We don't try for 0 as  # we included 0 as starting point in hamCycle()  for v in range(1,self.V): if self.isSafe(v, pos, path) == True: path[pos] = v if self.hamCycleUtil(path, pos+1) == True: return True # Remove current vertex if it doesn't  # lead to a solution  path[pos] = -1 return False def hamCycle(self): path = [-1] * self.V  ''' Let us put vertex 0 as the first vertex   in the path. If there is a Hamiltonian Cycle,   then the path can be started from any point   of the cycle as the graph is undirected ''' path[0] = 0 if self.hamCycleUtil(path,1) == False: print ('Solution does not exist
') return False self.printSolution(path) return True def printSolution(self, path): print ('Solution Exists: Following', 'is one Hamiltonian Cycle') for vertex in path: print (vertex ) # Driver Code  ''' Let us create the following graph   (0)--(1)--(2)   | /  |   | /  |   | /  |   (3)-------(4) ''' g1 = Graph(5) g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1,],[1, 1, 0, 0, 1], [0, 1, 1, 1, 0], ] # Print the solution  g1.hamCycle(); ''' Let us create the following graph   (0)--(1)--(2)   | /  |   | /  |   | /  |   (3) (4) ''' g2 = Graph(5) g2.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1], [0, 1, 0, 0, 1,], [1, 1, 0, 0, 0], [0, 1, 1, 0, 0], ] # Print the solution  g2.hamCycle(); # This code is contributed by Divyanshu Mehta>
C# 
// C# program for solution of Hamiltonian  // Cycle problem using backtracking using System; public class HamiltonianCycle {  readonly int V = 5;  int []path;  /* A utility function to check   if the vertex v can be added at   index 'pos'in the Hamiltonian Cycle  constructed so far (stored in 'path[]') */  bool isSafe(int v, int [,]graph,  int []path, int pos)  {  /* Check if this vertex is   an adjacent vertex of the  previously added vertex. */  if (graph[path[pos - 1], v] == 0)  return false;  /* Check if the vertex has already   been included. This step can be  optimized by creating an array  of size V */  for (int i = 0; i < pos; i++)  if (path[i] == v)  return false;  return true;  }  /* A recursive utility function  to solve hamiltonian cycle problem */  bool hamCycleUtil(int [,]graph, int []path, int pos)  {  /* base case: If all vertices   are included in Hamiltonian Cycle */  if (pos == V)  {  // And if there is an edge from the last included  // vertex to the first vertex  if (graph[path[pos - 1],path[0]] == 1)  return true;  else  return false;  }  // Try different vertices as a next candidate in  // Hamiltonian Cycle. We don't try for 0 as we  // included 0 as starting point in hamCycle()  for (int v = 1; v < V; v++)  {  /* Check if this vertex can be   added to Hamiltonian Cycle */  if (isSafe(v, graph, path, pos))  {  path[pos] = v;  /* recur to construct rest of the path */  if (hamCycleUtil(graph, path, pos + 1) == true)  return true;  /* If adding vertex v doesn't   lead to a solution, then remove it */  path[pos] = -1;  }  }  /* If no vertex can be added to Hamiltonian Cycle  constructed so far, then return false */  return false;  }  /* This function solves the Hamiltonian   Cycle problem using Backtracking. It   mainly uses hamCycleUtil() to solve the  problem. It returns false if there  is no Hamiltonian Cycle possible,   otherwise return true and prints the path.  Please note that there may be more than   one solutions, this function prints one   of the feasible solutions. */  int hamCycle(int [,]graph)  {  path = new int[V];  for (int i = 0; i < V; i++)  path[i] = -1;  /* Let us put vertex 0 as the first  vertex in the path. If there is a   Hamiltonian Cycle, then the path can be  started from any point of the cycle   as the graph is undirected */  path[0] = 0;  if (hamCycleUtil(graph, path, 1) == false)  {  Console.WriteLine('
Solution does not exist');  return 0;  }  printSolution(path);  return 1;  }  /* A utility function to print solution */  void printSolution(int []path)  {  Console.WriteLine('Solution Exists: Following' +  ' is one Hamiltonian Cycle');  for (int i = 0; i < V; i++)  Console.Write(' ' + path[i] + ' ');  // Let us print the first vertex again  // to show the complete cycle  Console.WriteLine(' ' + path[0] + ' ');  }  // Driver code  public static void Main(String []args)  {  HamiltonianCycle hamiltonian =  new HamiltonianCycle();  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3)-------(4) */  int [,]graph1= {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 1},  {0, 1, 1, 1, 0},  };  // Print the solution  hamiltonian.hamCycle(graph1);  /* Let us create the following graph  (0)--(1)--(2)  | /  |  | /  |  | /  |  (3) (4) */  int [,]graph2 = {{0, 1, 0, 1, 0},  {1, 0, 1, 1, 1},  {0, 1, 0, 0, 1},  {1, 1, 0, 0, 0},  {0, 1, 1, 0, 0},  };  // Print the solution  hamiltonian.hamCycle(graph2);  } } // This code contributed by Rajput-Ji>
Javascript 
>
PHP 
 // PHP program for solution of  // Hamiltonian Cycle problem // using backtracking  $V = 5; /* A utility function to check if  the vertex v can be added at index 'pos' in the Hamiltonian Cycle constructed so far  (stored in 'path[]') */ function isSafe($v, $graph, &$path, $pos) { /* Check if this vertex is   an adjacent vertex of the   previously added vertex. */ if ($graph[$path[$pos - 1]][$v] == 0) return false; /* Check if the vertex has already been included.  This step can be optimized by creating an array  of size V */ for ($i = 0; $i < $pos; $i++) if ($path[$i] == $v) return false; return true; } /* A recursive utility function  to solve hamiltonian cycle problem */ function hamCycleUtil($graph, &$path, $pos) { global $V; /* base case: If all vertices are included in  Hamiltonian Cycle */ if ($pos == $V) { // And if there is an edge from the  // last included vertex to the first vertex if ($graph[$path[$pos - 1]][$path[0]] == 1) return true; else return false; } // Try different vertices as a next candidate in // Hamiltonian Cycle. We don't try for 0 as we // included 0 as starting point hamCycle() for ($v = 1; $v < $V; $v++) { /* Check if this vertex can be added   to Hamiltonian Cycle */ if (isSafe($v, $graph, $path, $pos)) { $path[$pos] = $v; /* recur to construct rest of the path */ if (hamCycleUtil($graph, $path, $pos + 1) == true) return true; /* If adding vertex v doesn't lead to a solution,  then remove it */ $path[$pos] = -1; } } /* If no vertex can be added to Hamiltonian Cycle  constructed so far, then return false */ return false; } /* This function solves the Hamiltonian Cycle problem using Backtracking. It mainly uses hamCycleUtil() to solve the problem. It returns false if there is no Hamiltonian Cycle possible, otherwise return true and prints the path. Please note that there may be more than one solutions, this function prints one of the feasible solutions. */ function hamCycle($graph) { global $V; $path = array_fill(0, $V, 0); for ($i = 0; $i < $V; $i++) $path[$i] = -1; /* Let us put vertex 0 as the first vertex in the path.  If there is a Hamiltonian Cycle, then the path can be  started from any point of the cycle as the graph is  undirected */ $path[0] = 0; if (hamCycleUtil($graph, $path, 1) == false) { echo('
Solution does not exist'); return 0; } printSolution($path); return 1; } /* A utility function to print solution */ function printSolution($path) { global $V; echo('Solution Exists: Following is '. 'one Hamiltonian Cycle
'); for ($i = 0; $i < $V; $i++) echo(' '.$path[$i].' '); // Let us print the first vertex again to show the // complete cycle echo(' '.$path[0].' 
'); } // Driver Code /* Let us create the following graph (0)--(1)--(2)  | /  |  | /  |  | /  | (3)-------(4) */ $graph1 = array(array(0, 1, 0, 1, 0), array(1, 0, 1, 1, 1), array(0, 1, 0, 0, 1), array(1, 1, 0, 0, 1), array(0, 1, 1, 1, 0), ); // Print the solution hamCycle($graph1); /* Let us create the following graph (0)--(1)--(2)  | /  |  | /  |  | /  | (3) (4) */ $graph2 = array(array(0, 1, 0, 1, 0), array(1, 0, 1, 1, 1), array(0, 1, 0, 0, 1), array(1, 1, 0, 0, 0), array(0, 1, 1, 0, 0)); // Print the solution hamCycle($graph2); // This code is contributed by mits ?>>
Produzione 
Solution Exists: Following is one Hamiltonian Cycle 0 1 2 4 3 0 Solution does not exist>

Complessità temporale: O(N!), dove N è il numero di vertici.
Spazio ausiliario: O(1), poiché non viene utilizzato spazio aggiuntivo.

Nota: Il codice sopra stampa sempre un ciclo a partire da 0 . Il punto di partenza non dovrebbe avere importanza poiché il ciclo può essere avviato da qualsiasi punto. Se vuoi cambiare il punto di partenza, dovresti apportare due modifiche al codice sopra.
Cambia percorso[0] = 0; A percorso[0] = s ; Dove S è il tuo nuovo punto di partenza . Cambia anche il ciclo for (int v = 1; v