3

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
1
  • Se a identificação dos vértices do seu problema começar pela letra A, então recomendo que faça char v1 = 'A' + arvore[i].obterVertice1() - 1; quando for mostrar as arestas selecionadas. Além disso, ficaria melhor usar V+1 como tamanho do array subset (Pense no caso onde o numero de arestas é menor ou igual a V, então pode ocorrer acesso/escrita de memória fora dos limites do array).
    – Felipe
    Commented 6/07/2017 às 1:28

1 Resposta 1

1

Executei o programa e ele forneceu a seguinte saída (sem erros, e com os dados de entrada que você informou):

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

Acredito que o resultado 34 é o que está incorreto, pois a saída deveria ser a soma dos pesos das arestas selecionadas pelo algoritmo, portanto, ele deveria ser 48.

Se a afirmação acima é realmente o problema, ele está acontecendo devido ao código na linha:

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

Como a variável resultado vai acumluar o valor dos pesos, a forma correta para o cálculo é:

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

Após a execução (depois de feita a alteração), a saída do programa é:

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)

Referências consultadas:

O que é árvore geradora mínima?

Wikipedia - Algoritmo de Kruskal

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .