Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST (Minimum Spanning Tree) - Coggle Diagram
MST (Minimum Spanning Tree)
Subconjunto de arestas que conecta todos os vértices de um grafo sem formar ciclos e com o menor peso total possível.
Aplicações
Redes de computadores
Redes de distribuição (energia, água, etc.)
Clusterização
Estruturas de dados (filtragem mínima de conexões)
Kruskal
Gulosa (Greedy): sempre escolhe a aresta de menor peso que não forma ciclo
Usa estrutura de dados Union-Find para evitar ciclos
Ordena todas as arestas por peso crescente
Inicializa MST como conjunto vazio
Para cada aresta (u,v) na ordem:
3.1. Se u e v estão em componentes diferentes:
3.1.1. adiciona à MST e une os conjuntos
O(E log E) com Union-Find eficiente
Ideial para Grafos esparsos (poucas arestas)
Prim
Gulosa (Greedy): expande uma árvore iniciando por um vértice arbitrário
Usa fila de prioridade (heap) para escolher a aresta mínima conectando o vértice atual a um novo
Escolhe vértice inicial
Insere suas arestas válidas em uma heap
Repetidamente:
3.1. Escolhe aresta de menor peso conectando a um novo vértice
3.2. Adiciona vértice e novas arestas à heap
Com heap: O((V + E) log V)
Ideal para Grafos densos (muitas arestas)
Propriedades
Uniqueness:
Se todos os pesos são distintos -> MST é única
Subgrafo mínimo conexo
Não contém ciclos
Contém exatamente V − 1 arestas
Union-Find (Disjoint Set Union – DSU)
Kruskal para detectar ciclos
Controla componentes conectados
Find(x): Retorna representante do conjunto de x
Union(x, y): Une os conjuntos de x e y
Quase O(1), mais precisamente: O(α(n))
(função inversa de Ackermann)