C++ Busqueda de caminos en un grafo

Preguntas RecientesCategoria: OtroC++ Busqueda de caminos en un grafo
soydelITO preguntada 1 año antes

El programa se debe ser capas de encontrar todas las rutas posibles y mostrar una de esas rutas entre los nodos de un grafo. en este grafo los nodos son “ciudades” nombradas de la [a-k]. De entrada se debe de dar la letra de una ciudad y el programa mostrara una de todas las rutas posibles creadas que recorran varios nodos del grafo y regresen al origen.

1 Respuestas
snow Staff contestada 1 año antes

Aquí tienes tu código buen hombre

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>


using namespace std;
char ciudades[11] = {'a','b','c','d','e','f','g','h','i','j','k'};
char rutaAleatoria [20] = "";
bool imprimir = true;

//El grafo de la imagen se puede representar como una matriz, en donde cada
//posicion en columna y fila es una ciudad y en la interseccion de estas, estara
// el peso de su arista que las une, si hay ciudades que no tienen union
// tendran cero
int aristas [11][11] =
    {
        {0,20,0,99,78,47,0,0,0,0,0},
        {20,0,31,0,55,77,16,0,0,0,0},
        {0,31,0,0,0,8,1,75,0,0,0},
        {99,0,0,0,23,0,0,0,10,0,0},
        {78,55,0,23,0,9,0,0,18,21,0},
        {47,77,8,0,9,0,29,0,90,7,12},
        {0,16,1,0,0,29,0,80,0,18,27},
        {0,0,75,0,0,0,80,0,0,0,42},
        {0,0,0,10,18,0,0,0,0,25,0},
        {0,0,0,0,21,7,18,0,0,0,50},
        {0,0,0,0,0,12,37,42,0,50,0}

    };

int numeroAleatorio() {
    return rand() % 10;
}
//verifica que en la ruta no se reptia alguna ciudad en la que ya estuvimos
bool yaEstuvimos(char rutas[],char ciudad) {
    int tamArreglo  = sizeof(rutas) / sizeof(char);
    for( int i = 0; i &lt; tamArreglo; i++) {
        if(ciudad == rutas[i]) {
            return true;
        }
    }
    return false;
}

//dada la letra de la ciudad regresa su posicion en el arreglo de ciudades
// en la matriz tanto en la columna como en la fila es la misma posicion
int numeroCiudad(char letra) {
    int tamArreglo  = sizeof(ciudades) / sizeof(char);
    for( int i = 0; i < tamArreglo; i++) {
        if(letra == ciudades[i]) {
            return i;
        }
    }
    return -1;
}

bool buscarRuta(int numNodos,char ruta[], int indexRuta, char ciudadActual, char ciudadDestino,int profundidad) {
    if(profundidad == 7) {
        return false;
    }

    // contamos cuantos nodos va recorriendo, si no ha recorrido ninguno significa que apenas comenzo el
    // recorrido asi que evitamos preguntar si ya llego al destino o si ya estuvimos ahi
    if(numNodos > 0) {
        if(yaEstuvimos(ruta,ciudadActual)) {
            return false;
        }
        if(ciudadActual == ciudadDestino) {
            //una vez que encuentre una ruta en el grafo
            //generamos un nuemro aleatorio y si acierta a 5, imprimira esa ruta encontrada
            // y cambiara el valor de imprimir a falso para que ya no vuelva a imprimir otra ruta
            if(imprimir && numeroAleatorio() == 5) {
                printf("encontrada: %c%s%c\n",ciudadDestino,ruta,ciudadDestino);
                imprimir = false;
            }
        }
        ruta[indexRuta] = ciudadActual;
        indexRuta++;
    }
    numNodos++;
    profundidad++;
    //printf("%d,",numNodos);
    int posCiudadActual = numeroCiudad(ciudadActual);
    for(int i = 0; i < 11; i++) {
        if(aristas[posCiudadActual][i] > 0) {
            buscarRuta(numNodos,ruta,indexRuta,ciudades[i],ciudadDestino,profundidad);
        }

    }
    ruta[indexRuta] = 0;
    indexRuta--;
    return false;
}

int main()
{   srand(time(NULL));
    char ruta[15] = "";
    buscarRuta(0,ruta,0,'b','b',0);
    return 0;
}

Your Answer

0 + 14 =