Árvore Geradora Mínima (MST)

O que é uma árvore geradora

Num grafo conexo, uma árvore geradora é um subconjunto de arestas que:

• conecta todos os vértices;
• não tem ciclo.

Dessas duas condições sai um número fixo: toda árvore geradora tem exatamente V-1 arestas. Menos que isso e o grafo se parte; mais que isso e aparece ciclo, ou seja, uma aresta que não conecta nada de novo.

A árvore geradora mínima (MST) é a de menor soma de pesos. E ela responde uma pergunta muito concreta: qual o custo mínimo de infraestrutura para ligar tudo.

A propriedade do corte, que faz o guloso funcionar

Antes dos algoritmos, o motivo de eles funcionarem, que é uma ideia só e vale para os dois.

Pegue qualquer forma de dividir os vértices em dois grupos (um corte). Olhe todas as arestas que cruzam de um grupo para o outro. A mais barata delas pode entrar na MST com segurança.

A intuição do porquê: os dois grupos precisam se conectar de alguma forma, então alguma aresta que cruza o corte tem que estar na árvore. Se a árvore usasse uma mais cara, você poderia trocá-la pela mais barata e obter uma árvore ainda válida e mais barata. Logo, escolher a mais barata nunca é errado.

Kruskal e Prim são duas formas de aplicar essa propriedade repetidamente. Só muda como cada um escolhe o corte.

Kruskal: ordene as arestas e vá colando

Kruskal ignora a estrutura e olha só a lista de arestas:

1. Ordene todas as arestas por peso.
2. Percorra da mais barata para a mais cara.
3. Se a aresta liga dois vértices que ainda não estão conectados, aceite. Se já estão, ela formaria ciclo: recuse.
4. Pare quando tiver V-1 arestas.

def kruskal(n, arestas):
    arestas.sort(key=lambda e: e.peso)
    pai = list(range(n))

    def acha(x):
        while pai[x] != x:
            pai[x] = pai[pai[x]]      # compressão de caminho
            x = pai[x]
        return x

    total, mst = 0, []
    for e in arestas:
        ra, rb = acha(e.a), acha(e.b)
        if ra == rb:
            continue                  # mesmo grupo: faria ciclo
        pai[ra] = rb                  # une os dois grupos
        total += e.peso
        mst.append(e)
    return total, mst

Rode o Kruskal e olhe as cores dos vértices: elas são os grupos. No começo cada vértice é a própria ilha, e cada aresta aceita funde duas ilhas. A árvore cresce em pedaços soltos que só no fim viram uma coisa só, o que é a característica visual do Kruskal.

Repare nas arestas riscadas: são as recusadas por ligarem dois vértices que já estavam no mesmo grupo.

O union-find, em duas linhas de ideia

A pergunta "esses dois já estão conectados?" precisa ser respondida uma vez por aresta, e responder com um percurso a cada vez custaria caro demais. O union-find (ou DSU, disjoint set union) responde em tempo praticamente constante.

A estrutura é um vetor: cada elemento aponta para um "pai", e o representante de um grupo é quem aponta para si mesmo. Duas otimizações fazem toda a diferença:

• Compressão de caminho: ao subir procurando a raiz, aproveite e ligue os nós direto nela.
• União por tamanho ou rank: ao unir dois grupos, pendure o menor no maior, para a árvore não crescer.

Com as duas, cada operação custa O(α(n)), com α sendo a função inversa de Ackermann, que vale no máximo 4 para qualquer n que caiba no universo. Na prática, constante.

Prim: faça a árvore crescer

Prim ataca pelo outro lado. Em vez de olhar arestas soltas, ele mantém uma árvore só e a faz crescer:

1. Comece com um vértice qualquer.
2. Olhe todas as arestas que saem da árvore para fora dela.
3. Pegue a mais barata e traga o vértice novo para dentro.
4. Repita até todo mundo estar dentro.

import heapq

def prim(inicio, adj):
    dentro = {inicio}
    fila = [(p, inicio, v) for v, p in adj[inicio]]
    heapq.heapify(fila)
    total, mst = 0, []

    while fila:
        peso, u, v = heapq.heappop(fila)
        if v in dentro:
            continue                       # entrou por outro lado
        dentro.add(v)
        total += peso
        mst.append((u, v))
        for w, p in adj[v]:
            if w not in dentro:
                heapq.heappush(fila, (p, v, w))
    return total, mst

Troque para o modo Prim no visualizador e note a diferença visual: agora existe uma única mancha crescendo a partir do A, e nunca pedaços soltos.

Se esse código parece o Dijkstra, é porque quase é. A única diferença é o que vai na fila: o Dijkstra empurra dist[u] + peso (o custo acumulado desde a origem), e o Prim empurra peso (o custo daquela aresta só). Um constrói caminhos, o outro constrói uma rede.

Kruskal ou Prim

Na prática o custo é parecido, e a escolha costuma ser por conveniência. Se as arestas já vêm numa lista, Kruskal é mais direto. Se você tem lista de adjacência e o grafo é denso, Prim evita ordenar E arestas.

Rode os dois no preset com pesos repetidos: eles escolhem arestas diferentes e o peso total é o mesmo. Esse é o fato importante: a MST pode não ser única, mas o peso mínimo é.

O que a MST não faz

Vale reforçar os limites, porque eles caem em prova:

• Não dá caminho mínimo. Rode o preset "ponte cara" e repare: a aresta de peso 20 entra na MST porque sem ela o grafo se parte, mesmo sendo horrível para qualquer rota.
• Não funciona em grafo dirigido. Ali o problema equivalente se chama arborescência mínima e o algoritmo é outro (Edmonds).
• Precisa de grafo conexo. Se não for, o que existe é uma floresta geradora mínima, uma árvore por componente. O Kruskal produz isso naturalmente; o Prim precisa ser reiniciado em cada componente.
• Peso negativo não é problema. Diferente do Dijkstra, aqui não existe hipótese de "só somar": Kruskal e Prim funcionam com pesos negativos sem alteração nenhuma.

Onde aparece

O nome já entrega: os problemas originais eram literalmente redes.

• Redes elétricas e de telecomunicação: o problema que motivou o algoritmo de Borůvka em 1926, para eletrificar a Morávia com o menor custo de cabo.
• Projeto de rede e clustering: remover as k-1 arestas mais caras de uma MST divide os pontos em k grupos, e isso é um algoritmo de clusterização legítimo (single-linkage).
• Aproximação para o caixeiro viajante: percorrer a MST dá uma rota no máximo 2 vezes pior que a ótima, e a heurística de Christofides melhora isso para 1,5.
• Segmentação de imagens e análise de circuitos, pelo mesmo raciocínio de conectar com custo mínimo.

Como praticar

Min Cost to Connect All Points é a MST sem disfarce: os pontos são vértices, a distância Manhattan entre eles é o peso, e o grafo é completo (o que favorece o Prim). É o melhor lugar para escrever os dois e comparar.

Connecting Cities With Minimum Cost é o mesmo problema com o grafo já dado, e é onde o Kruskal fica mais natural. Aproveite para implementar o union-find com compressão de caminho do zero: você vai reusar essa estrutura muitas vezes.

Depois, Number of Operations to Make Network Connected e Redundant Connection treinam o union-find sozinho, sem MST, que é a forma como ele mais aparece em entrevista.

Uma dica de leitura: as palavras "conectar todos", "custo mínimo para ligar" e "rede" indicam MST. As palavras "do ponto A ao ponto B" indicam caminho mínimo. São problemas diferentes com algoritmos diferentes, e reconhecer isso na primeira leitura economiza a maior parte do tempo.

Com este tópico o grupo de grafos fecha o caminho principal: representação, percursos, caminho mínimo com Dijkstra, Bellman-Ford e A*, ordem de dependências e agora conectividade de custo mínimo.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 2:12:12.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.