circuito hamiltoniano

[xKuZz]

Te recomiendo que empieces de 0 la parte del circuito hamiltoniano. Creo que no has entendido muy bien el algoritmo para implementarlo. Ya que te urge y yo necesito ya irme a dormir te voy a dejar un código que hice hace un tiempo que resuelve ese algoritmo y en el que está aplicando todo al detalle (creo). Ten en cuenta que copiar y pegar no te va a servir porque utilizo cosas como los vectores de la STL, algoritmos de la STL y funciones lambda de C++11 que estaba empezando a utilizar por aquel entonces. Utilízalo como referencia y adáptalo a las cosas que tu estás utilizando. Mucha suerte.

Código C++:

/* @file: ciclohamilton.cpp
   @brief: Comprueba si hay un ciclo de Hamilton en el grafo por fuerza bruta.
           El grafo viene representado por la matriz de adyacencia
   @author: xKuZz
*/
 
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef vector < vector <int> > int_2;
 
bool usar(const int &vertice, const int_2 &grafo, const vector<int> &camino, const int &posicion){
    // CUMPLIR LAS DOS CONDICIONES SIGUIENTES IMPLICA QUE ES UN POSIBLE VÉRTICE SIGUIENTE EN EL CAMINO
    bool USAR=true;
   // Compruebo que el vértice sea adyacente al anterior
    if (grafo[camino[posicion-1]][vertice]==0)
        USAR=false;
   // Si es adyacente compruebo también que no esté en el camino utilizado
    for_each(camino.begin(),camino.end(),[&](int i=0){if (camino[i]==vertice) USAR=false;});
    return USAR;
}
 
bool HamiltonRecursivo(const int_2 &grafo, vector<int> &camino, const int &posicion){
   // ESTA ES UNA MANERA RECURSIVA DE COMPROBAR QUE UN CAMINO ES DE HAMILTON
    bool hamiltoniano=false;
 
    // CASO FINAL: si posición es igual al tamaño del vector camino
 
    if (posicion==camino.size())
        hamiltoniano=grafo[camino[posicion-1]][0]; // Devuelvo si adyacen o no el principio y el final del ciclo
 
    else { // CASO NO FINAL
 
        // IMPLEMENTACIÓN RECURSIVA: PROBAMOS TODOS LOS VÉRTICES MENOS EL 0 ya que lo hemos considerado el inicial
        for (int v=1; v < camino.size(); v++){
        
        // UTILIZO LA FUNCIÓN PARA COMPROBAR EL VÉRTICE
                if (usar(v, grafo, camino, posicion)){
 
                        camino[posicion] = v; // METO EL VÉRTICE SI LA COMPROBACIÓN ES CORRECTA
 
                        // UTILIZO ESTA FUNCIÓN EN RECURRENCIA PARA AVERIGUAR EL RESTO DEL CAMINO
                        if(HamiltonRecursivo (grafo, camino, posicion+1))
                    return true;
 
                    // SI EL VERTICE NO ME LLEVA HACIA LA SOLUCIÓN PONGO UN -1 PARA INDICARLO
                            camino[posicion] = -1;
            }
            }
        }
            
    return hamiltoniano;    
        
}
 
bool CicloHamilton(vector<int> &sol, const int_2 &grafo){
    // Sol es el camino solución obtenido
    // Devuelve TRUE si hay ciclo de Hamilton
    // Dicho ciclo de Hamilton se guarda en el vector sol
    
    // DIMENSIONO LA MATRIZ PARA ALMACENAR EL CAMINO
    sol.resize(grafo.size());
    // RELLENO LA MATRIZ DE -1
    fill(sol.begin(),sol.end(),-1);
    // El primer dato será un 0
    sol[0]=0;
 
    // LLAMO AL MÉTODO RECURSIVO
    if (!HamiltonRecursivo(grafo, sol, 1))
        {
            cout << "No hay solución";
            return false;
    }
    else{
        cout << "Existe solución";
        // SACO LA SOLUCIÓN DE MI CAMINO (MUESTRO CADA VALOR DEL VECTOR)    
        for_each(sol.begin(),sol.end(),[&](int i=0){cout << "-> " << sol[i];});
        cout << endl;
        return true;
    }
}
 
 
 
 
int main(){ // COMPROBACIONES
vector<int> solucion;
int_2 grafin;
grafin.resize(3,vector<int>(3));
cout << "PRIMER GRAFO: TIENE QUE SALIR DE HAMILTON\n";
grafin[0][0]=0; grafin[0][1]=1; grafin [0][2]=1;
grafin[1][0]=1; grafin[1][1]=0; grafin [1][2]=1;
grafin[2][0]=1; grafin[2][1]=1; grafin [2][2]=0;
CicloHamilton(solucion,grafin);
cout << "SEGUNDO GRAFO: NO TIENE QUE SALIR DE HAMILTON\n";
grafin[0][0]=0; grafin[0][1]=0; grafin [0][2]=0;
grafin[1][0]=0; grafin[1][1]=0; grafin [1][2]=0;
grafin[2][0]=0; grafin[2][1]=0; grafin [2][2]=1;
CicloHamilton(solucion,grafin);
}