Tema: Algoritmo de PRIM Error?
Ver Mensaje Individual
  #1 (permalink)  
Antiguo 14/10/2013, 21:45
ambigus
 
Fecha de Ingreso: septiembre-2008
Mensajes: 221
Antigüedad: 16 años, 2 meses
Puntos: 1
Algoritmo de PRIM Error?
En este código:

Código C++: 
Ver original
  1. #include <iostream>
  2. #include "Grafo.h"
  3. #include "windows.h"
  4. #define infinito 9999
  5. #define no_visitado -1
  6. //---------------------------------------------------------------------//
  7. using namespace std;
  8. //---------------------------------------------------------------------//
  9. struct estructura_etiqueta{
  10.             int padre;
  11.             int costo;
  12.        };
  13. //---------------------------------------------------------------------//
  14. void cargar_grafo(Grafo<int> &grafo1)
  15. {
  16.     grafo1.agregarVertice(1);
  17.     grafo1.agregarVertice(2);
  18.     grafo1.agregarVertice(3);
  19.     grafo1.agregarVertice(4);
  20.     grafo1.agregarVertice(5);
  21.     grafo1.agregarVertice(6);
  22.     grafo1.agregarVertice(7);
  23.     grafo1.agregarArco(1,2,3);
  24.     grafo1.agregarArco(2,1,3);
  25.     grafo1.agregarArco(1,4,3);
  26.     grafo1.agregarArco(4,1,3);
  27.     grafo1.agregarArco(2,5,2);
  28.     grafo1.agregarArco(5,2,2);
  29.     grafo1.agregarArco(2,3,1);
  30.     grafo1.agregarArco(3,2,1);
  31.     grafo1.agregarArco(3,5,3);
  32.     grafo1.agregarArco(5,3,3);
  33.     grafo1.agregarArco(4,3,2);
  34.     grafo1.agregarArco(3,4,2);
  35.     grafo1.agregarArco(4,7,3);
  36.     grafo1.agregarArco(7,4,3);
  37.     grafo1.agregarArco(5,6,1);
  38.     grafo1.agregarArco(6,5,1);
  39.     grafo1.agregarArco(6,7,2);
  40.     grafo1.agregarArco(7,6,2);
  41.     cout << grafo1 << endl;
  42. }
  43. //---------------------------------------------------------------------//
  44. bool existe_en_lista(int nodo, list<int> vertices_visitados)
  45. {
  46.     list<int>::const_iterator iterador;
  47.     bool existe = false;
  48.     for(iterador = vertices_visitados.begin(); iterador != vertices_visitados.end(); iterador++)
  49.         if(*iterador == nodo)
  50.             existe = true;
  51.     return existe;
  52. }
  53. //---------------------------------------------------------------------//
  54. int extraer_minimo(Grafo<int> grafo1, list<int> &vertices, list<int> &vertices_visitados, estructura_etiqueta etiqueta[])
  55. {
  56.     list<int>::const_iterator iterador;
  57.     int costo, origen, destino;
  58.     costo = infinito;
  59.     for(iterador = vertices_visitados.begin(); iterador != vertices_visitados.end(); iterador++)
  60.     {
  61.         list<Grafo<int>::Arco> adyacentes;
  62.         grafo1.devolverAdyacentes(*iterador, adyacentes);
  63.         list<Grafo<int>::Arco>::const_iterator iterador_adyacente;
  64.         for(iterador_adyacente = adyacentes.begin(); iterador_adyacente != adyacentes.end(); iterador_adyacente++)
  65.             if(existe_en_lista(iterador_adyacente->devolverAdyacente(), vertices_visitados) == false)
  66.                 if(costo > grafo1.costoArco(*iterador, iterador_adyacente->devolverAdyacente()))
  67.                 {
  68.                     costo = grafo1.costoArco(*iterador, iterador_adyacente->devolverAdyacente());
  69.                     origen = *iterador;
  70.                     destino = iterador_adyacente->devolverAdyacente();
  71.                 }  
  72.     }
  73.     etiqueta[destino].padre = origen;
  74.     etiqueta[destino].costo = costo;
  75.     return destino;
  76. }
  77. //---------------------------------------------------------------------//
  78. void Prim(Grafo<int> grafo1, estructura_etiqueta etiqueta[], list<int> &vertices, list<int> &vertices_visitados)
  79. {
  80.     list<int>::const_iterator iterador;
  81.     iterador = vertices.begin();
  82.     etiqueta[*iterador].costo = 0;
  83.     etiqueta[*iterador].padre = 0;
  84.     vertices_visitados.push_front(*iterador);
  85.     vertices.remove(*iterador);
  86.     while(!vertices.empty())
  87.     {
  88.         int nodo = extraer_minimo(grafo1, vertices, vertices_visitados, etiqueta);
  89.         vertices_visitados.push_back(nodo);
  90.         vertices.remove(nodo);
  91.     }
  92. }
  93. //---------------------------------------------------------------------//
  94. int main()
  95. {
  96.     Grafo<int> grafo1;
  97.     cargar_grafo(grafo1);
  98.     list<int> vertices;
  99.     grafo1.devolverVertices(vertices);
  100.     list<int>::const_iterator iterador;
  101.     estructura_etiqueta etiqueta[vertices.size()];
  102.     for(iterador = vertices.begin(); iterador != vertices.end(); iterador++)
  103.     {
  104.         etiqueta[*iterador].padre = no_visitado;
  105.         etiqueta[*iterador].costo = infinito;
  106.     }
  107.     list<int> vertices_visitados;
  108.     Prim(grafo1, etiqueta, vertices, vertices_visitados);
  109.     cout << "//-----------------PRIM-------------//" << endl << endl;
  110.     list<int>::const_iterator iterador_visitados;
  111.     for(iterador_visitados = vertices_visitados.begin(); iterador_visitados != vertices_visitados.end(); iterador_visitados++)
  112.     {
  113.         cout << "//------------------------------//" << endl;
  114.         cout << "Nodo: " << *iterador_visitados << endl;
  115.         cout << "Padre: " << etiqueta[*iterador_visitados].padre << endl;
  116.         cout << "Costo: " << etiqueta[*iterador_visitados].costo << endl;
  117.     }
  118.     return 0;
  119. }
  120. //---------------------------------------------------------------------//



OBSERVAR:

Cita:
estructura_etiqueta etiqueta[vertices.size()];

DUDA: El cod no esta funcionando en la linea que te dije del main es porq se esta declarando un vector en cero pero al cambiarlo por una declaracion constante sigue arrojando un error

¿SOLUCIÓN?

Gracias de antemano!