Kruskal Algorithm problem C ++

4

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
    
asked by anonymous 27.06.2015 / 05:26

1 answer

1

I ran the program and it provided the following output (no errors, and 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 that the result 34 is incorrect because the output should be the sum of the weights of the edges selected by the algorithm, so it should be 48 .

If the above statement is really the problem, it is happening because of the code in the line:

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

As the variable result will accumulate the value of the weights, the correct form for the calculation is:

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

After the execution (after the change is made), the program exit 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 a tree minimum?

Wikipedia - Kruskal Algorithm

    
31.01.2016 / 14:23