emilio_s83
20 de Junio del 2004

`Por favor necesito urgente una implementacion en c++ para determinar caminos hamiltonianos en grafos,
gracias!!!

neo20
20 de Junio del 2004

Hola emilio ,
Te pongo un algoritmo que hice hace dos años , a ver si te sirve:
void inicializar_RobertsFlores(int *k,int *temp,int *inicio,int *camino,char *vector_p,int count,char *argv[])
{
int i;
for (i=0;i<=count;i++)//ver despues;
{
camino[i]=-1;
temp[i]=0;
}
(*k)=-1;

(*inicio)=buscar_vertice(vector_p,count,(*(argv)[4]));
}

void RobertsFlores(int *mat,int *camino,int count,int inicio,int *k,int *temp,int p,int comp)
{

int m,i=0,j=0,n=0;

if(camino[0]==-1)
{
(*k)++;
camino[0]=inicio;
temp[inicio]=1;
}
while((*k)<count-1)
{
p++;
while(comp<count)
{
m=comparar_iguales_vertices(camino,k,comp,inicio);
if((*(mat+inicio*count+comp)!=0)&&(m==1)&&(temp[comp]==0))
{
(*k)++;
camino[(*k)]=comp;
temp[comp]=1;
inicio=comp;
comp=0;
break;
}
else
comp++;
}
if(comp==count)
{
comp=inicio+1;
temp[inicio]=0;
camino[(*k)]=-1;
(*k)--;
inicio=camino[(*k)];
}
RobertsFlores(mat,camino,count,inicio,k,temp,p,comp);
}


}

int comparar_iguales_vertices(int *camino,int *k,int var, int inicio)
{
int i,cont=0;
for (i=0;i<=(*k);i++)
{
if ((camino[i]==var))
cont++;
}
if (cont==0)
return 1;
else
return 0;
}


void imprimir_pantalla_fichero_Roberts(int k,int *camino,int *mat,char *vector_p,int count,char *argv[])
{

int i,j=0;
FILE *fichero;
fichero=fopen(argv[5],"w");
printf("n");
if (fichero==NULL)
{
printf("Error en obrir fitxer de dades per escriure. n");
exit(1);
}
if (k>=0)
{

for (i=0;i<k;i++)
{
printf("%c-%c:%dn",vector_p[(camino[i])],vector_p[(camino[i+1])],*(mat+(camino[i])*count+(camino[i+1])));
fprintf(fichero,"%c-%c:%dn",vector_p[(camino[i])],vector_p[(camino[i+1])],*(mat+(camino[i])*count+(camino[i+1])));
j=j+(*(mat+(camino[i])*count+(camino[i+1])));
}
printf("camino con peso : %dn",j);
fprintf(fichero,"camino con peso : %dn",j);
}
fclose(fichero);


}


si kieres todo el codigo ,mandame un mail: