Prim - MST ( Minimum Spanning Tree )

Situação problema: Queremos fazer a fiação de uma cidade com o menor custo.

Implementação em C++11

Complexidade O ( V² )

#include <bits/stdc++.h> using namespace std; #define pb push_back #define INF 0x3f3f3f #define fi first #define se second typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef tuple<int,int,int> iii; vvii AdjList; vector<bool> vstd; void init( int vertex ) { // Inicializa AdjList e vértices como não visitados AdjList.clear(); AdjList.resize(vertex); vstd.clear(); vstd.resize(vertex, false); } int MST_PRIMM( int from ) { // Marca o vertice como visitado vstd[from] = true; int mst = 0; // Priority queue de ( peso , saída, chegada ) priority_queue< iii , vector<iii>, greater<iii> > pq; // Add todos as arestas relacionas com o vértice selecionado for( auto v : AdjList[from] )

pq.push( iii( v.se , from, v.fi ) ); while( !pq.empty() ) { iii v = pq.top(); pq.pop(); int f = get<1>(v), a = get<2>(v), w = get<0>(v); /* No tipo iii sempre colocamos o vértice de saída no meio, então não precisamos verificá-lo, somente o vértice de chegada, então: */ if( !vstd[a] ) { /* Adicionamos o peso da aresta e marcamos como visitado Se precisar aqui também pode ser adicionadas as arestas da Arvore Geradora Minima já que temos saída(f), chegada(a) e peso(w) */ mst += w; vstd[a] = true; /* Novamente adicionamos todas as arestas o vértice selecionado e verificamos se o vértice de chegada foi visitado se não foi então adicionamos na priority queue */ for( auto v : AdjList[a] )

if( !vstd[v.fi] )

pq.push( iii( v.se , a , v.fi ) ); } } return mst; } int main() { int vertex, edges; int from, arrival, weight; scanf("%d%d", &vertex, &edges); init(vertex); for (int i = 0; i < edges ; ++i) { scanf("%d%d%d", &from, &arrival, &weight); AdjList[from].pb( { arrival , weight } ); AdjList[arrival].pb( { from , weight } ); } printf("%d\n", MST_PRIMM(0) ); return 0; }