Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Algoritmo de PRIM Error?

Estas en el tema de Algoritmo de PRIM Error? en el foro de C/C++ en Foros del Web. En este código: @import url("http://static.forosdelweb.com/clientscript/vbulletin_css/geshi.css"); Código C++: Ver original #include <iostream> #include "Grafo.h" #include "windows.h" #define infinito 9999 #define no_visitado -1 //---------------------------------------------------------------------// using namespace std ...
  #1 (permalink)  
Antiguo 14/10/2013, 21:45
 
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!
  #2 (permalink)  
Antiguo 14/10/2013, 21:46
 
Fecha de Ingreso: septiembre-2008
Mensajes: 221
Antigüedad: 16 años, 2 meses
Puntos: 1
Respuesta: Algoritmo de PRIM Error?

GRAFO.H: http://ideone.com/1N5dfc

Etiquetas: funcion, int, struct
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 15:56.