C   407
hamiltonian.c
Guest on 31st May 2022 05:15:59 PM


  1. #include <stdio.h>
  2. #include<stdbool.h>
  3. int g[10][10];
  4. int x[10];
  5. int flag=0;
  6. int n,start;
  7. void hamiltonian(int k)
  8. {
  9.     x[1]=start;
  10.     do
  11.     {
  12.         nextvalue(k);
  13.         if( x[k] == 0) return;
  14.         if(k==n)
  15.         {
  16.             flag=1;
  17.             for(int i=1;i<=n;i++)
  18.             printf("%d    ",x[i]);
  19.               printf("\n");
  20.         }
  21.         else
  22.         hamiltonian(k+1);
  23.     }
  24.     while(true);
  25. }
  26. void nextvalue(int k)
  27. {
  28.     int j=0;
  29.     do{
  30.         x[k]=(x[k]+1)%(n+1);
  31.         if(x[k]==0) return;
  32.         if(g[x[k-1]][x[k]]==1)
  33.         {
  34.             for(j=1;j<=k-1;j++)
  35.                 if(x[j]==x[k]) break;
  36.                 if(j==k)
  37.                     if(  k<n || ((k==n) && g[x[n]][x[1]]==1))
  38.                      return;
  39.         }
  40.     }
  41.     while(true);
  42. }
  43.  
  44. int main() {
  45.  
  46.         scanf("%d",&n); //total no of vertices
  47.         for(int i=1;i<=n;i++)
  48.         {
  49.             for(int j=1;j<=n;j++)
  50.             scanf("%d",&g[i][j]);
  51.         }
  52. //      printf("Enter starting node\n");
  53.         scanf("%d",&start); //starting node
  54.         hamiltonian(2);
  55.         if(!flag)
  56.         printf("Hamilton  cycle does not exist\n");
  57.         return 0;
  58. }
  59.  
  60. /* INPUT:
  61.    6
  62. 0 1 1 0 0 1
  63. 1 0 1 0 0 1
  64. 1 1 0 1 0 0
  65. 0 0 1 0 1 0
  66. 0 0 0 1 0 1
  67. 1 1 0 0 1 0
  68. 1
  69.  
  70. OUTPUT:
  71. 1    2    3    4    5    6    
  72. 1    2    6    5    4    3    
  73. 1    3    4    5    6    2    
  74. 1    6    5    4    3    2  
  75.  
  76. */
Raw Paste

Login or Register to edit or fork this paste. It's free.