Grafos: Árvores Geradoras Mínimas (MST)

Metáfora e Motivação

Imagine que você é o governador de um estado e sua missão é interligar 5 cidades distintas com fibra óptica espacial ultracara. Você não precisa (nem tem dinheiro) para conectar todas as cidades entre si formando um pentagrama. Você só quer a garantia absoluta de que, saindo de qualquer cidade, você consiga pingar/alcançar qualquer outra gastando o mínimo absurdo de cabo.

A malha ideal matemática que soluciona esse problema para você se chama Árvore Geradora Mínima (Minimum Spanning Tree - MST).

Uma árvore no mundo dos grafos significa estritamente isso: 1. Conecta todo mundo. 2. Não possui “Ciclos”! (Um ciclo significaria que você gastou dinheiro num elo inútil pra fechar uma roda gigante). 3. Utiliza exatamente V - 1 arestas em relação aos V vértices.

Como construir os Ramos?

Dois pesquisadores antigos mapearam as duas formas definitivas de caçar e plugar a malha perfeita:

1. Algoritmo de Kruskal (O Preferido de Torneios)

Este senhor confia totalmente numa regra Gulosa agressiva em $\mathcal{O}(E \log E)$: * Liste todos os orçamentos (arestas) das estradas do país. Reordene-as do MENOR peso para o MAIOR. * Analise a menor de todas. Essa rua forma um ciclo visual fechado na sua obra em andamento? * Se Não: Ótimo! Compre a rua, ligue as cidades. * Se Sim: Jogue a proposta no lixo (uma rua paralela barata não adianta se já estão linkadas por outros meios). * Avance na lista.

2. Algoritmo de Prim

Lembra o Dijkstra: * Você joga uma base numa cidade aleatória. Você mapeia com radar (Priority Queue) todas as estradas que saem dessa cidade pro mundo inexplorado. Você expande na MENOR artéria disponível para as terras que ainda não pisou. * Perfeito para grafos Ultra Densos (Quase todo mundo ligado a todo mundo), beirando $O(V^2)$ se não otimizar.

O Motor do Kruskal: C++ DSU (Disjoint Set Union)

Para saber magicamente “Essa cidade X já está colada / no mesmo continente que a cidade Y para não fechar ciclo?”, não rodamos infinitas BFS/DFS que seriam letais. Usamos e construímos o lendário e veloz Union-Find (DSU). Ele acha quem é o Líder de Matilha/Raiz de X e se for o mesmo que Y, bingo, eles já estão casados.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cassert>

using namespace std;

// Representação: Vértice A, Vértice B, Peso da Aresta
typedef tuple<int, int, int> Aresta; 

// Estrutura do DSU Clássico
struct UnionFind {
    vector<int> pai, rank;
    UnionFind(int n) {
        pai.resize(n); rank.resize(n, 0);
        for(int i=0; i<n; i++) pai[i] = i; // Cada um começa sendo seu próprio líder
    }
    
    int encontrar(int i) { // Path Compression (Achatamento O(1))
        if(pai[i] == i) return i;
        return pai[i] = encontrar(pai[i]);
    }
    
    // Une o bloco do i no do j
    bool unir(int i, int j) { 
        int raiz_i = encontrar(i);
        int raiz_j = encontrar(j);
        
        if(raiz_i == raiz_j) return false; // Formaria Ciclo! Já são irmãos!
        
        // Colando matilhas por tamanho/rank otimizado
        if(rank[raiz_i] < rank[raiz_j]) pai[raiz_i] = raiz_j;
        else if(rank[raiz_i] > rank[raiz_j]) pai[raiz_j] = raiz_i;
        else {
            pai[raiz_j] = raiz_i;
            rank[raiz_i]++;
        }
        return true; // União bem sucedida
    }
};

int rodarKruskal(int V, vector<Aresta>& arestas) {
    int custoTotalMST = 0;
    int arestas_linkadas = 0;
    
    UnionFind dsu(V);
    
    // Sort das arestas. Como o tuplo testa index [0], devemos indexar O Peso lá (ver abaixo)
    sort(arestas.begin(), arestas.end());

    // Varredura gulosa - Começa do barato até o caro
    for(auto t : arestas) {
        int w = get<0>(t);
        int u = get<1>(t);
        int v = get<2>(t);
        
        // Tenta plugar U no V
        if(dsu.unir(u, v)) {
            custoTotalMST += w; // Construímos a ponte
            arestas_linkadas++;
            if(arestas_linkadas == V - 1) break; // MST completa.
        }
    }
    
    return custoTotalMST;
}

void executando_testes() {
    int V = 4;
    vector<Aresta> arestas; // <Peso, Origem, Destino>
    
    // Grafo quadrado cruzado 
    arestas.push_back(make_tuple(10, 0, 1));
    arestas.push_back(make_tuple(6, 0, 2));
    arestas.push_back(make_tuple(5, 0, 3));
    arestas.push_back(make_tuple(15, 1, 3));
    arestas.push_back(make_tuple(4, 2, 3));
    // Ordem Gulosa q ele pegará: (4 de 2-3), (5 de 0-3), (6 de 0-2 CICLO! IGNORA!), (10 de 0-1)
    
    // Somatória: 4 + 5 + 10 = 19
    int mst = rodarKruskal(V, arestas);
    assert(mst == 19);

    cout << "[✅] Testes de Kruskal DSU validados garantindo MST.\n";
}

int main() {
    executando_testes();
    return 0;
}

Exercício Guiado (Iluminação do Reino)

Problema: Beecrowd 1152 - Estradas Escuras

A infraestrutura cobra R$ 1,00 para iluminar cada metro. Queremos desligar ruas redundantes onde cidadãos possam transitar de lanterna mas, de uma ponta à outra do país principal, os carros consigam chegar via luminárias da via conectada principal. O que o prefeito quer saber: Qual a economia máxima em Reais?

Raciocínio DSU: Rode primeiro um laço computando as vias normais: Total Real = Sum(Todos os Pesos do Input). Imediatamente empilhe todos em array vector<tuple<W, U, V>>. Dispare seu próprio Kruskal(V, arr) local para descobrir o menor esqueleto de sobrevida do país que custará X reais de luz. Finalmente, retorne no seu programa Total Real - X (que é todo o luxo das vias ramificadas descartadas pelo guloso)!

Listagem de Extensão Clássica

Ache os atalhos e crie redes para redes elétricas, tubulações, estradas rurais através do treinamento mental em DSU: