Created
December 22, 2016 19:09
-
-
Save brun0xff/c88a7f379be1cc5a54a0f2fd24a0b408 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> // sort | |
#include <string.h> // memset | |
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 | |
vector<Aresta> arestas; // vetor de arestas | |
public: | |
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 | |
int kruskal() | |
{ | |
int soma=0; | |
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[V]; | |
// inicializa todos os subconjuntos como conjuntos de um único elemento | |
memset(subset, -1, sizeof(int) * V); | |
for(int i = 0; i < size_arestas; i++) | |
{ | |
int v1 = buscar(subset, arestas[i].obterVertice1()); | |
int v2 = buscar(subset, arestas[i].obterVertice2()); | |
if(v1 != v2) | |
{ | |
// se forem diferentes é porque NÃO forma ciclo, insere no vetor | |
soma += arestas[i].obterPeso(); | |
//cout << arestas[i].obterPeso(); | |
arvore.push_back(arestas[i]); | |
unir(subset, v1, v2); // faz a união | |
} | |
} | |
return soma; | |
} | |
}; | |
int main(int argc, char *argv[]) | |
{ | |
int m , n; | |
int peso; | |
int a,b; | |
while(true){ | |
cin >> m >> n; | |
if(m==0&& n==0)break; | |
Grafo g(m+1); // grafo | |
for(int i=0; i<n; i++) | |
{ | |
cin >> a >> b >> peso; | |
g.adicionarAresta(a,b, peso); | |
//g = adicionarAresta(g,a, b, peso); | |
} | |
int soma = g.kruskal(); // roda o algoritmo de Kruskal | |
cout << soma << endl; | |
//g.arestas.clear(); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment