Hamiltonian Cycle

Hamiltonian Cycle.cpp

/*
Ciclul hamiltonian se poate determina folosind spatiul permutarilor filtrate de matricea de adiacenta a grafului.

Input:
numar de noduri si nodul de start
5 1
0 1 0 0 1
1 0 1 1 0
0 1 0 1 1
0 0 1 0 1
1 0 0 1 0
*/


#include <iostream>
#define FIN "graf.in"
#define SIZE 100

using namespace std;

const int N = 50;

int path[ N ], 

    matrix[ N ][ N ], 

    used[ N ],

    start_node, n;

void print_solution() {

	  for(int i = 1; i <= n; ++i) cout<<path[i]<<" ";

      cout<<start_node;   	  	

  cout<<endl;
}

void hamilton(int k) {

     if(k == n + 1) {

     	  if( matrix[start_node][ path[k - 1] ] ) {

     	  	   print_solution();
     	  } 

     	  
     } else {

                 for(int v = 1; v <=n; ++v) {

                 	 if(!used[ v ] && matrix[path[k-1]][v]) {

                 	 	 path[k] = v;
                 	 	 used[v] = 1;
                 	 	 hamilton(k+1);
                 	 	 used[v] = 0;
                 	 }
                 }
     
     }

}    

int main(int argc, char const *argv[])
{

	freopen(FIN, "r", stdin);

	cin>>n>>start_node;

	path[1] = start_node;

    for(int i = 1; i <=n ;++i) used[i] = 0;

    used[start_node] = 1;


    for(int i = 1; i <= n; ++i) {
    	 for(int j = 1; j<=n; j++) {
    	 	cin>>matrix[i][j];
    	 }    	 
    }

    cout<<"Numarul de Varfuri: "<<n<<" ";
    cout<<"start Node: "<<start_node<<"\n";

    for(int i = 1; i <= n; ++i) {
    	 for(int j = 1; j<=n; j++) {
    	 	cout<<matrix[i][j]<<" ";
    	 }    	 

    	 cout<<endl;
    }

    //Generarea ciclului hamiltonian
    hamilton( 2 );
 
	
	return 0;
}