Foro de elhacker.net

Aquí pongo un código que estoy haciendo por si a alguien le hiciera falta.

Sirve para representar grafos y en el ejemplo lo combino con un pequeño mapa de 7x7 con colisión por así decirlo.

#include <iostream>
using namespace std;
///////////////////////////////////////////////
///////////////////////////////////////////////
class Map2D {// Esta clase es para generar una matrix de 2dimensiones
    public://sirvepara crear un mapa con cordenadas 'x' e 'y'
        Map2D(int,int);
        bool mMap[100][100];//bool es para que solo tome 2 valores posibles true'1' y false'0' en el mapa false es colisión y true es libre 
        void Print();// esto para imprimir el mapa
        void Add(int,int);// esto lo he echo para añadir una colisión
        int mSizeX;//esto es el tamaño del ancho del mapa, pueden tomar como valor máximo 100 por el tamaño de la matrix mMap...
        int mSizeY;//esto es el tamaño del alto del mapa, pueden tomar como valor máximo 100 por el tamaño de la matrix mMap...
};
Map2D::Map2D(int _x,int _y){
    mSizeX=_x;
    mSizeY=_y;
    for(int y=0;y<_y;y++){
        for(int x=0;x<_x;x++){
            mMap[y][x]=false;//el mapa se crea vacio.
        }
    }
}
void Map2D::Print(){//esto nada más es para imprimir el mapa
    for(int y=0;y<mSizeY;y++){
        for(int x=0;x<mSizeX;x++){
            cout << mMap[y][x];
        }
        cout << endl;
    }
    cout << endl;
}
void Map2D::Add(int x,int y){// Esto es para añadir una colisión un tontería puesto que los miembros son publicos en la clase
    mMap[y][x]=true;//nada más lo hice para ahorrar trabajo, puesto con poner (Map2D::Add(x,y) 'x' e 'y' son cordenadas.) añade colision
}
 
///////////////////////////////////////////////
///////////////////////////////////////////////
class StructMatricial {// Esta clase es para crear una estructura matricial de tipo conjunto, sirve para trabajar con grafos
    public:
        StructMatricial();
        bool Load(Map2D);
        int mVertices[100];//vertices que tiene el grafo
        int mAristas[100][10];//una arista es el camino que une un vertice con otro. por ejemplo si el vertice '1' tiene una arista que conecta con el vertice '2' sería así mAristas[1][0]=2
        int mNumerosAristas[100];//Para saber el numero de aristas que tiene cada vertice, "caminos hacia otros vertices"
        bool mIsVertice[100];//esta es una matriz complementaría para saber si el vertice es transitable o no, si no es colision ese punto entonces es transitable
};
 
StructMatricial::StructMatricial(){
}
 
bool StructMatricial::Load(Map2D m){
    int iv=0;//iterador vertices
    int ia=0;//iterador aristas
    //Primero Creamos todos los vertices
    for(int y=0;y<m.mSizeY;y++){
        for(int x=0;x<m.mSizeX;x++){
            mVertices[iv]=iv;//
            if(m.mMap[y][x]==false){//Si la posicion no es colision
                mIsVertice[iv]=false;//la posicon es un vertice transitable
            }
            else mIsVertice[iv]=true;//Si no, no lo es
            // incremento del iterador
            iv++;
 
        }
    }
    iv=0;
    for(int y=0;y<m.mSizeY;y++){
        for(int x=0;x<m.mSizeX;x++){
            if(m.mMap[y][x]==false){
                if(m.mMap[y][x-1]==false && x>0){// si izquierda no es colision .. el x>0 es para que no se salga de memoria la operación
                    mAristas[iv][ia]=mVertices[((y*m.mSizeX)+x-1)];// entoncens el vertice tiene una arista hacia el vertice de la izquierda
                    ia++;
                }
                if(m.mMap[y][x+1]==false && x<m.mSizeX){
                    mAristas[iv][ia]=mVertices[(y*m.mSizeX)+x+1];
                    ia++;
                }
                if(m.mMap[y-1][x]==false && y>0){
                    mAristas[iv][ia]=mVertices[((y-1)*m.mSizeX)+x];
                    ia++;
                }
                if(m.mMap[y+1][x]==false && y<m.mSizeY){
                    mAristas[iv][ia]=mVertices[((y+1)*m.mSizeX)+x];
                    ia++;
                }
            }
            // incremento del iterador
            mNumerosAristas[iv]=ia;
            iv++;
            ia=0;
 
        }
    }
    return false;
};
///////////////////////////////////////////////
///////////////////////////////////////////////
 
 
///////////////////////////////////////////////
///////////////////////////////////////////////
int main(int argc,char* argv[]){
    ///////////////////////////////////////////
    // Creación del mapa
    Map2D map(7,7);
    map.Add(3,2);
    map.Add(4,1);
    map.Add(2,3);
    map.Add(4,3);
    for(int i=0;i<7;i++)map.Add(i,0);
    for(int i=0;i<7;i++)map.Add(i,6);
    for(int i=0;i<7;i++)map.Add(0,i);
    for(int i=0;i<7;i++)map.Add(6,i);
    map.Print();
    ///////////////////////////////////////////
    // Creación de la estructura matricial conjunto
    StructMatricial SM;// Trollface con el nombre
    SM.Load(map);
    ///////////////////////////////////////////
    ///////////////////////////////////////////
    cout << "vertice: "<< SM.mVertices[24]<< endl;
    cout << "Aristas: ";
    for(int i=0;i<SM.mNumerosAristas[24];i++)cout << SM.mAristas[24][i] << "-" ;
    cout << endl;
    cout << "Game Over" << endl;
    return 0;
}

Pues, dejame decirte que muy buen esfuerzo, pero no se entiende lo que haces, podrias explicar un poco de que se trata?

Entiendo que generas una matriz 7x7, y la generas llenandola con "0" y vas cambiando determinados puntos. Pero, veo que usas clases, todavia no he llegado a ese apartado en C++, como se trabaja??

Buen código, pero a la hora de cargarlo sale esto:


Lo saque en codeblocks, pero no se que quieres decir ni con vertice ni con aristas.
Muy confuso lo que tratas de hacer, me gustaria mucho que explicaras como trabaja cada función y las clases, si no es mucho pedir, aparte de eso, es un trabajo genial colega!

Soy malo explicando pero he modificado el código añadiendo comentarios, Este código puede servir para hacer el código de el camino más corto, quizás haya otras formas no lo sé, sobre las clases pues la uso para dividir el trabajo en plan, esto pertenece a esto y esto otro a esto. esta semilla es de manzana y esta otra semilla de pera, jeje.

y sobre lo que se imprime es lo siguiente.
el mapa, 1 colisión y 0 no colisión, imagina un mapa de ciudad y tienes que trazar el camino más corto hasta el cine, no vale hacer una linea recta por que hay edificios en medio, pues entonces ponemos un 1.
donde pone vértice es el vértice que quiero examinar y donde aristas son las aristas que tiene el vértice que comunica con otros vértices, osea el 9 y el 15 que te salió son otros vértices, la arista almacena el vértice al que conecta. Espero haber explicado lo mejor posible esto.
Cualquier cosa avisa.

Si quieres información sobre la grafos visita este link. http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos