MST Fuerza Bruta

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
using namespace std;

#define M 1000
enum V {A, B, C, D, E};

struct arista{
  V o;//origen
  V d;//destino
  short w;
  arista(V o, V d, short w) : o(o), d(d), w(w) {}
};

vector<arista*> aristas;
vector<bool> nodos;
short nNodos = 5;

void generarGrafo(){
  aristas.push_back(new arista(A,B,9));
  aristas.push_back(new arista(A,C,8));
  aristas.push_back(new arista(A,E,5));
  aristas.push_back(new arista(B,C,6));
  aristas.push_back(new arista(B,D,1));
  aristas.push_back(new arista(B,E,4));
  aristas.push_back(new arista(C,D,2));
  aristas.push_back(new arista(D,E,3));
  for(short i=0; i<nNodos; i++)
    nodos.push_back(false);
}

inline bool existe(vector<short>* A, short &id){
  for(short i=0; i<A->size(); i++)
    if(A->at(i)==id) return true;
  return false;
}
inline bool valida(short o, short d){
  return (!(nodos[o] && nodos[d]));
}

vector<short>* MST(){
  vector<short>* A = new vector<short>;
  for(short i = 1; i<nNodos; i++){
    short id = 0;
    short id_min = 0;
    short min = 1000;
    for(arista* e : aristas){
      if(!existe(A, id) && valida(e->o, e->d) && min > e->w){
        min = e->w;
        id_min = id;
      }
      id++;
    }
    A->push_back(id_min);
    nodos[aristas[id_min]->o]=true;
    nodos[aristas[id_min]->d]=true;
  }
  return A;
}

string nombre(short nodo){
  switch(nodo){
    case A: return "A";
    case B: return "B";
    case C: return "C";
    case D: return "D";
    case E: return "E";
  }
  return "";
}

string nombrarArista(short id){
  return nombre(aristas[id]->o) + " - " +
         nombre(aristas[id]->d);
}

int main() {
  generarGrafo();
  vector<short>* res = MST();
  cout << "El MST contiene las siguientes aristas: " << endl;
  for(short e_id : *res)
    cout << " " << nombrarArista(e_id) << endl;
  return 0;
}