I'm implementing the Kruskal algorithm, but I'm having a problem because it's losing one of the links and its value, I already did an implementation in Dijkstra, but in the work I'm doing, Kruskal is the best one to be done, I'm not finding the hole in the code.
If someone can tell me what's wrong, thank you right away, I'll leave the code information below.
#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;
}
The entry I am using is as follows:
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