Árvore Geradora Mínima (Minimum Spanning Tree - MST)

1. Conectando Cidades com Custo Mínimo

Imagine que você é um engenheiro de telecomunicações. Você precisa passar cabos de fibra óptica conectando \(N\) cidades. Você sabe o custo para cabear entre qualquer par de cidades. Objetivo: Conectar todas as cidades gastando o mínimo possível.

A solução é uma subestrutura do grafo original que: 1. Contém todos os vértices. 2. É conexa. 3. Não tem ciclos (é uma árvore). 4. A soma dos pesos das arestas é mínima.

Isso é uma MST. Se o grafo tem \(V\) vértices, a MST terá exatamente \(V-1\) arestas.

2. Algoritmo de Kruskal (Abordagem Gulosa nas Arestas)

O algoritmo de Joseph Kruskal é intuitivo: “Sempre tente pegar a aresta mais barata disponível, desde que ela não forme um ciclo”.

Passo a Passo

  1. Crie uma lista com todas as arestas do grafo.
  2. Ordene a lista por peso crescente.
  3. Itere pela lista ordenada:
    • Seja a aresta \((u, v)\) com peso \(w\).
    • Se \(u\) e \(v\) já estão conectados (estão no mesmo conjunto), discarte a aresta (formaria ciclo).
    • Se não, adicione a aresta à MST e una os conjuntos de \(u\) e \(v\).

Para verificar conectividade e unir conjuntos rapidamente, usamos a estrutura Union-Find (DSU).

Implementação Java (Kruskal)

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, weight;
    public Edge(int u, int v, int w) {
        this.u = u; this.v = v; this.weight = w;
    }
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class KruskalMST {
    
    // Union-Find Simplificado (veja tópico 19 para completo)
    static int[] parent;
    static int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    static void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) parent[rootI] = rootJ;
    }

    public static int kruskal(int V, List<Edge> edges) {
        Collections.sort(edges); // O(E log E)
        
        parent = new int[V];
        for(int i=0; i<V; i++) parent[i] = i;
        
        int mstWeight = 0;
        int edgesCount = 0;
        
        for (Edge e : edges) {
            if (find(e.u) != find(e.v)) {
                union(e.u, e.v);
                mstWeight += e.weight;
                edgesCount++;
            }
        }
        
        if (edgesCount != V - 1) return -1; // Grafo desconexo
        return mstWeight;
    }
}

Complexidade: \(O(E \log E)\) devido à ordenação.

3. Algoritmo de Prim (Abordagem Gulosa nos Vértices)

O algoritmo de Robert Prim (e Jarník) “cresce” a MST a partir de um vértice inicial, similar ao Dijkstra.

Passo a Passo

  1. Escolha um vértice inicial arbitrário (ex: 0).
  2. Adicione todas as arestas dele numa Priority Queue (Min-Heap).
  3. Marque o vértice como visitado.
  4. Enquanto a PQ não estiver vazia:
    • Remova a aresta \((u, v)\) de menor peso.
    • Se \(v\) já foi visitado, ignore.
    • Se não, esta aresta faz parte da MST! Adicione o custo.
    • Marque \(v\) como visitado e adicione todas as arestas saindo de \(v\) para a PQ.

Implementação Java (Prim)

class Pair implements Comparable<Pair> {
    int v, weight;
    // construtor...
    public int compareTo(Pair other) { return this.weight - other.weight; }
}

public static int prim(int V, List<List<Pair>> adj) {
    boolean[] visited = new boolean[V];
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    
    // Começa do 0, custo 0
    pq.add(new Pair(0, 0));
    
    int mstWeight = 0;
    int nodesCount = 0;
    
    while (!pq.isEmpty()) {
        Pair current = pq.poll();
        int u = current.v;
        
        if (visited[u]) continue; // Lazy deletion
        
        visited[u] = true;
        mstWeight += current.weight;
        nodesCount++;
        
        for (Pair neighbor : adj.get(u)) {
            if (!visited[neighbor.v]) {
                pq.add(new Pair(neighbor.v, neighbor.weight));
            }
        }
    }
    
    if (nodesCount != V) return -1;
    return mstWeight;
}

Complexidade: \(O(E \log V)\) usando Binary Heap.

4. Kruskal vs Prim: O Veredito

Característica Kruskal Prim
Lógica Ordena arestas. Cresce árvore (Priority Queue).
Estrutura Auxiliar Union-Find (DSU). Heap (Priority Queue) + Visited array.
Melhor para Grafos Esparsos (poucas arestas). Grafos Densos (muitas arestas).
Facilidade Muito fácil se tiver DSU pronto. Fácil se souber Dijkstra.

Em competições, Kruskal é geralmente o favorito porque o DSU é muito curto de implementar e a lógica de ordenar arestas é menos propensa a bugs do que gerenciar a PQ.

Back to top