Un archivo fuente en C++ que demuestra el uso de un grafo. Viene con una imágen que indica como están conectados los nodos

tarea.jpg

PLAIN TEXT
C++:
  1. #include <iostream.h>
  2. #include <stdlib.h>
  3. #include <set>
  4. #include <string>
  5. #include <stack>
  6. #include <list>
  7. /* Esta clase contiene un nodo y su lista de adyacencia
  8. * que contiene los nodos que estan a su alrededor
  9. */
  10. class Vertice
  11. {
  12.       public:
  13.              string nombre;
  14.              set <Vertice*> arcos;
  15.  
  16.              Vertice(){}
  17.              Vertice(string const &inicio) : nombre(inicio) {}
  18.  
  19.              void nuevoArco(Vertice &v){ arcos.insert(&v); }
  20. };
  21.  
  22. set<Vertice*> alcanzable(Vertice&);
  23. int totalArcos(Vertice*, int);
  24.  
  25. int main()
  26. {
  27.     //inicializacion de los vertices
  28.     Vertice* grafoSinPeso = new Vertice[8];
  29.     grafoSinPeso[0] = Vertice("Mexico");
  30.     grafoSinPeso[1] = Vertice("Puebla");
  31.     grafoSinPeso[2] = Vertice("Cuernavaca");
  32.     grafoSinPeso[3] = Vertice("Toluca");
  33.     grafoSinPeso[4] = Vertice("Chiapas");
  34.     grafoSinPeso[5] = Vertice("Chihuahua");
  35.     grafoSinPeso[6] = Vertice("San Luis");
  36.     grafoSinPeso[7] = Vertice("Pachuca");
  37.  
  38.     //añadimos sus uniones entre si
  39.  
  40.     grafoSinPeso[0].nuevoArco(grafoSinPeso[2]);  grafoSinPeso[0].nuevoArco(grafoSinPeso[3]);
  41.     grafoSinPeso[1].nuevoArco(grafoSinPeso[0]);
  42.     grafoSinPeso[2].nuevoArco(grafoSinPeso[1]);
  43.     grafoSinPeso[3].nuevoArco(grafoSinPeso[2]);  grafoSinPeso[3].nuevoArco(grafoSinPeso[4]);   grafoSinPeso[3].nuevoArco(grafoSinPeso[5]);
  44.     grafoSinPeso[4].nuevoArco(grafoSinPeso[2]);  grafoSinPeso[4].nuevoArco(grafoSinPeso[5]);
  45.     grafoSinPeso[5].nuevoArco(grafoSinPeso[6]);
  46.    // grafoSinPeso[6].nuevoArco(grafoSinPeso[3]);   // no hay de Sn luis a Toluca
  47.     grafoSinPeso[7].nuevoArco(grafoSinPeso[5]);
  48.  
  49.    // mostramos todos las uniones
  50.  
  51.    for(int i = 0; i <8; i++)
  52.    {
  53.            set<Vertice*> resultado;
  54.            resultado = alcanzable(grafoSinPeso[i]);//, resultado);
  55.  
  56.            cout <<"las ciudades que se pueden alcanzar desde " <<grafoSinPeso[i].nombre <<" son:" <<endl;
  57.  
  58.            set<Vertice*> :: iterator itr;
  59.            for(itr = resultado.begin(); itr != resultado.end(); ++itr)
  60.           // for(itr = grafoSinPeso[i].arcos.begin(); itr != grafoSinPeso[i].arcos.end(); itr++)
  61.               cout << (*itr)->nombre <<" " <<endl;
  62.    }
  63.        cout <<"El numero total de arcos es: " <<totalArcos(grafoSinPeso, 8) <<endl;
  64.       system("PAUSE");
  65.       return 0;
  66. }
  67.  
  68. /* Este metodo nos regresa un conjunto de vertices a los que se puede llegar desde el nodo de parametro
  69. * es decir, todos los nodos para los cuales existe un camino, que no esten aislados.
  70. */
  71.  
  72. set<Vertice*> alcanzable(Vertice &inicio)
  73. {
  74.      //al principio, asumimos ningun nodo se puede alcanzar
  75.  
  76.      //creamos una pila de los nodos que faltan de visitar
  77.      //comenzamos con el primer nodo que es el parametro
  78.      set<Vertice*> resultado;
  79.      stack <Vertice *> verticesPendientes;
  80.      verticesPendientes.push(&inicio);
  81.  
  82.      //sacamos los vertices uno a uno
  83.  
  84.      while(!verticesPendientes.empty())
  85.      {
  86.           Vertice *ptr = verticesPendientes.top();
  87.           verticesPendientes.pop();
  88.                //si no lo habiamos visitado, lo marcamos
  89.           if(resultado.count(ptr) == 0)
  90.           {
  91.              resultado.insert(ptr);
  92.  
  93.              //añadimos ahora las ciudades a las que se pueden llegar desde el punto en donde
  94.              // estamos
  95.  
  96.          set<Vertice*>::iterator inicio = ptr->arcos.begin();
  97.          set<Vertice*>::iterator fin = ptr->arcos.end();
  98.  
  99.          for(; inicio != fin; inicio++)
  100.                verticesPendientes.push(*inicio);
  101.           }
  102.  
  103.      }//while
  104.  
  105.      return resultado;
  106. }//alcanzable
  107.  
  108. /* Contamos todos los arcos que existen entre los nodos
  109. */
  110.  
  111. int totalArcos(Vertice* raiz, int lon)
  112. {
  113.      int total = 0;
  114.      for(int i = 0; i <lon; i++)
  115.      {
  116.          Vertice *ptr = &(raiz[i]);
  117.          set<Vertice*>::iterator inicio = ptr->arcos.begin();
  118.          set<Vertice*>::iterator fin = ptr->arcos.end();
  119.  
  120.          for(; inicio != fin; inicio++)
  121.                total++;
  122.      }//for
  123.      return total;
  124. }

Popularidad: 7%