Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST (Minimum Spanning Tree) - Coggle Diagram
MST
(Minimum Spanning Tree)
O que é uma MST?
MST = Árvore Geradora Mínima
Subconjunto de arestas que conecta todos os vértices de um grafo sem ciclos, com peso total mínimo
Só faz sentido em grafos conexos e ponderados
Objetivo: ligar todos os pontos com o menor custo possível
Ex: redes de energia, internet, estradas, cabos, etc.
Propriedades da MST
Sempre tem V - 1 arestas (V = nº de vértices)
Pode haver mais de uma MST com mesmo peso total
Arestas com pesos iguais podem empatar
Abordagem geral
Algoritmos gulosos
(greedy)
Prim
Começa em um vértice qualquer
Vai crescendo a árvore, escolhendo a aresta de menor peso que conecta um vértice visitado a um não visitado
1° Escolhe um vértice inicial
2° Marca como visitado
3° Adiciona à árvore a aresta mais barata que
conecta a árvore a um novo vértice
4° Repete até incluir todos os vértices
Estrutura usada:
Min-Heap (fila de prioridade),
para escolher a menor aresta rapidamente
Árvore começa em A
A → B (custo 1)
B → C (custo 2)
...
Kruskal
Começa com todos os vértices isolados
Ordena as arestas por peso
Vai adicionando as menores arestas, evitando ciclos
1° Ordena todas as arestas por peso crescente
2° Para cada aresta (u, v):
Se u e v não estão conectados, adiciona a aresta
Senão, ignora (formaria ciclo)
Estrutura usada:
Union-Find (com
path compression e union by rank)
arestas: A-B(1), A-C(3), B-C(2), C-D(4)
ordena: A-B, B-C, A-C, C-D
vai adicionando e unindo conjuntos
Union-Find (estrutura de Kruskal)
Find(x) → encontra o conjunto de x
Union(x, y) → une os conjuntos de x e y
Path Compression → encurta caminho ao buscar
Union by Rank → junta conjuntos menores aos maiores
Evita que a estrutura fique lenta
Quando usar qual?
Prim: melhor para grafos densos
Kruskal: melhor para grafos esparsos
Aplicações
Construção de redes (telefonia, estradas, cabos)
Otimização de conexões em sistemas distribuídos