Se citeşte matricea de adiacenţă a unui graf. Să se determine dacă graful este hamiltonian.

Soluţie: vom folosi metoda backtracking, aplicată asupra unei stive în care vom păstra nodurile care compun lanţul. Vom porni de la primul nod şi vom putea adăuga în stivă doar un nod adiacent. De asemenea, nodul adăugat nu trebuie să se regăsească pe nivelurile anterioare. Dacă am atins în stivă numărul total de noduri iar nodul final este adiacent cu nodul iniţial, am găsit soluţia problemei.


#include "stdio.h"
#include "conio.h"
int stiva[100],n,m,k,nr_solutii,a[20][20];
int verifica()
{
  int i;
  if(k>1)
    //dacă a[st[k-1]][st[k]] este 0 returnăm 0
    if(!a[stiva[k-1]][stiva[k]])
       return 0;
    else
      //dacă a [stiva[k-1]][stiva [k]] este 1 căutam pe toate nivelurile
      //anterioare nivelului curent
      for(i=1;i <= k-1;i++)         //dacă nodul curent se găseşte pe unul din nivelurile         //anterioare returnăm 0         if(stiva[i] == stiva[k])           return 0;         //dacă stiva conţine toate nodurile grafului         if(k == n)           //iar ultimul nod nu este adiacent cu primul nod returnăm 0           if(!a[stiva[1]][stiva[k]])             return 0;   return 1; }
void tipareste_solutie()
{
  int i;
  for(i=1;i <= n;i++)     printf("%d ",stiva[i]);   putchar("\n");   //forţăm ieşirea după găsirea primei soluţii   k=0;   nr_solutii++; } void cauta() {   //pornim de la nivelul iniţial 1   k=l;   //când k va descreşte la o algoritmul se încheie   while(k > 0)
    if(stiva[k]