hamilton.c

来自「树的算法」· C语言 代码 · 共 50 行

#include "algo.h"
#include <stdio.h>
#define NUM 5
void hamilton(int n, int x[], int c[][NUM])
{
  int i,z,k;
  int cnt=0;
  int* s=malloc(sizeof(int)*NUM);
  for (i=0; i<n; i++){
    x[i]=-1;
    s[i]=0;
  }
  k=1; s[0]=1; x[0]=0;

  while (k>-0){
    x[k]=x[k]+1;
    while (x[k]<n)
      if (!s[x[k]]&&c[x[k-1]][x[k]])
        break;
      else
        x[k]=x[k]+1;
    if ((x[k]<n) && (k!=n-1)){
      s[x[k]]=1; k=k+1;
    }
    else if ((x[k]<n) && (k==n-1) && c[x[k]][x[0]])
    {
      printAnswer(x,n,cnt++);
      k--; x[k]++;
    }
    else{
      x[k]=-1; k=k-1; s[x[k]]=0;
    }
  }
  free(s);
}
int main()
{
  int c[][NUM]={
    0,1,0,1,0,
    1,0,1,1,1,
    0,1,0,1,1,
    1,1,1,0,1,
    0,1,1,1,0
  };
  int n=5;
  int x[NUM];
  hamilton(5,x,c);

}