Estou implementando o algoritmo de Kruskal, só que estou com um problema porque ele esta perdendo uma das ligações e o valor dela, eu já fiz uma implementação em Dijkstra, só que no trabalho que estou fazendo o Kruskal é o melhor a ser feito, eu não estou achando o furo no código.
Se alguém puder me dizer oque esta de errado agradeço desde já, vou deixar as informações do código abaixo.
#include <iostream>
#include <vector>
#include <algorithm> // sort
#include <string.h> // memset
#include <stdio.h>
using namespace std;
class Aresta
{
int vertice1, vertice2, peso;
public:
Aresta(int v1, int v2, int peso)
{
vertice1 = v1;
vertice2 = v2;
this->peso = peso;
}
int obterVertice1()
{
return vertice1;
}
int obterVertice2()
{
return vertice2;
}
int obterPeso()
{
return peso;
}
// sobrescrita do operador "<"
bool operator < (const Aresta& aresta2) const
{
return (peso < aresta2.peso);
}
};
class Grafo
{
int V; // número de vértices
public:
vector<Aresta> arestas; // vetor de arestas
Grafo(int V)
{
this->V = V;
}
// função que adiciona uma aresta
void adicionarAresta(int v1, int v2, int peso)
{
Aresta aresta(v1, v2, peso);
arestas.push_back(aresta);
}
// função que busca o subconjunto de um elemento "i"
int buscar(int subset[], int i)
{
if(subset[i] == -1)
return i;
return buscar(subset, subset[i]);
}
// função para unir dois subconjuntos em um único subconjunto
void unir(int subset[], int v1, int v2)
{
int v1_set = buscar(subset, v1);
int v2_set = buscar(subset, v2);
subset[v1_set] = v2_set;
}
/// função que roda o algoritmo de Kruskal
void kruskal()
{
vector<Aresta> arvore;
int size_arestas = arestas.size();
// ordena as arestas pelo menor peso
sort(arestas.begin(), arestas.end());
// aloca memória para criar "V" subconjuntos
int * subset = new int[arestas.size()];
// inicializa todos os subconjuntos como conjuntos de um único elemento
memset(subset, -1, sizeof(int) * arestas.size());
for(int i = 0; i < size_arestas; i++)
{
int v1 = buscar(subset, arestas[i].obterVertice1());
int v2 = buscar(subset, arestas[i].obterVertice2());
printf("%d %d\n", v1, v2);
if(v1 != v2)
{
// se forem diferentes é porque NÃO forma ciclo, insere no vetor
arvore.push_back(arestas[i]);
unir(subset, v1, v2); // faz a união
}
}
int size_arvore = arvore.size();
int resultado = 0;
// mostra as arestas selecionadas com seus respectivos pesos
for(int i = 0; i < size_arvore; i++)
{
char v1 = 'A' + arvore[i].obterVertice1();
char v2 = 'A' + arvore[i].obterVertice2();
cout << "(" << v1 << ", " << v2 << ") = " << arvore[i].obterPeso() << endl;
resultado = arvore[i].obterPeso() + arvore[i].obterPeso();
}
cout << resultado;
}
};
int main(int argc, char *argv[])
{
int x, y;
int inicio, fim, peso;
scanf("%d %d", &x, &y);
//cin >> x >> y;
Grafo g(x); // grafo
for( int i = 0; i < y; i++){
// adiciona as arestas
//fflush(stdin);
//cin >> inicio >> fim >> peso;
scanf("%d %d %d", &inicio, &fim, &peso);
g.adicionarAresta(inicio, fim, peso);
}
for( int i = 0; i < y; i++){
printf("%d %d %d\n", g.arestas[i].obterVertice1(), g.arestas[i].obterVertice2(), g.arestas[i].obterPeso());
}
g.kruskal(); // roda o algoritmo de Kruskal
return 0;
}
A entrada que estou usando é a seguinte:
7 12
1 3 6
1 4 9
2 3 17
2 5 32
2 7 27
3 4 11
3 5 4
4 5 3
4 6 19
5 6 13 //Essa é a origem o destino e o peso que o algoritmo perde.
5 7 15
6 7 5