Kruskal’s algorithm problem C++

Question

I’m implementing Kruskal’s algorithm, only I’m having a problem because he’s missing one of the links and the value of it, I’ve already made an implementation in Dijkstra, only in the work I’m doing Kruskal is the best to be done, I’m not finding the hole in the code.

If anyone can tell me what’s wrong I appreciate it now, 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’m 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

Answer 1

I ran the program and it provided the following output (no errors, and with the input data you entered):

4 5
3 5
6 7
1 5
5 5
5 5
5 7
7 7
2 7
7 7
7 7
7 7
(E, F) = 3
(D, F) = 4
(G, H) = 5
(B, D) = 6
(F, G) = 13
(C, D) = 17
34

I believe the result 34 is what is incorrect, because the output should be the sum of the edges weights selected by the algorithm, therefore it should be 48.

If the above statement is really the problem, it is happening due to the code on the line:

resultado = arvore[i].obterPeso() + arvore[i].obterPeso();

As the variable outworking will collect the value of the weights, the correct form for the calculation is:

resultado += arvore[i].obterPeso();

After execution (after the change is made), the output of the program is:

4 5
3 5
6 7
1 5
5 5
5 5
5 7
7 7
2 7
7 7
7 7
7 7
(E, F) = 3
(D, F) = 4
(G, H) = 5
(B, D) = 6
(F, G) = 13
(C, D) = 17
48
RUN SUCCESSFUL (total time: 4s)

References consulted:

What is minimum generating tree?

Wikipedia - Kruskal’s algorithm