Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 4: Graphs Parte 2: 4.3: Minimum Spanning Tree - Coggle Diagram
Capítulo 4: Graphs Parte 2: 4.3: Minimum Spanning Tree
Conceito de MST
MST = Minimum Spanning Tree (Árvore Geradora Mínima)
É uma árvore que conecta todos os vértices de um grafo ponderado não direcionado com peso total mínimo.
Usada em:
Conexões de rede (custo mínimo)
Planejamento de cabos, estradas, tubulações, etc.
Propriedades
Tem exatamente V−1 arestas (onde V é o número de vértices).
Deve ser conexa e sem ciclos.
Pode haver mais de uma MST com mesmo peso mínimo.
Algoritmos Principais
A. Kruskal’s Algorithm
Abordagem greedy.
Seleciona arestas de menor peso sem formar ciclo.
Usa estrutura Union-Find (Disjoint Set) para detectar ciclos.
Complexidade: O(E log E)
(E = número de arestas)
Etapas:
Ordenar as arestas por peso crescente.
Percorrer as arestas e incluir na MST se não formar ciclo.
Parar quando tiver V−1 arestas.
B. Prim’s Algorithm
Também greedy, mas baseado em expansão de vértices.
Constrói MST a partir de um vértice inicial, adicionando sempre a menor aresta que conecta um novo vértice.
Implementação eficiente com priority queue.
Complexidade: O(E log V)
Diferenças com Kruskal:
Kruskal considera arestas (ordenação global).
Prim considera vértices (crescimento local).
Variantes Importantes
A. Second Best Spanning Tree
Estratégia:
Remover uma aresta do MST e substituir por outra não usada (arestas “chord”).
Recalcular o custo total → menor custo maior que o da MST original.
Complexidade: O(VE)
Útil em problemas de redundância ou caminhos alternativos.
Objetivo: encontrar uma segunda MST com custo ligeiramente maior.
B. Minimum Spanning Subgraph
Algumas arestas já são obrigatórias.
O grafo resultante pode não ser uma árvore pura.
Continuar adicionando arestas de menor custo até conectar o grafo.
C. Maximum Spanning Tree
Inverso da MST: maximiza o peso total.
Modificação simples de Kruskal: ordenar arestas em ordem decrescente.
D. Minimum Spanning Forest
Se o grafo não é totalmente conexo, gera uma floresta mínima (várias MSTs).
Parar quando o número de componentes conectados atingir K.
E. Second Best ST
Encontra a MST e depois testa trocas de arestas para achar a segunda melhor.
Usa estrutura para marcar e testar arestas substituídas.
F. Minimax / Maximin Path
Objetivo: minimizar o maior peso em um caminho entre dois vértices.
Solução: usar a MST e procurar o máximo peso na rota MST(i, j).