Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST, Algoritmo de Prim, Algoritmo de Kruskal, Disjoint Subsets (Union…
MST
Minimum Spanning Tree
Definição
Subconjunto de arestas que:
Conecta todos os vértices do grafo
Sem formar ciclos (árvore)
Com peso total mínimo
Requisitos
Grafo conexo e não direcionado
Aplicações
Redes de computadores
Distribuição elétrica/água
Roteamento e clustering
Algoritmo de Prim
Complexidade:
O(V²) com matriz de adjacência
O((V + E) log V) com heap + lista de adjacência
Estratégia: cresce a árvore a partir de um vértice
Utiliza: fila de prioridade (min-heap)
Escolhe a aresta de menor peso que conecta à árvore
Evita ciclos automaticamente
Ideal para grafos densos
Algoritmo de Kruskal
Complexidade:
O(E log E) (ordenação + union-find)
Estratégia: ordena todas as arestas e adiciona as menores
Usa estrutura Union-Find (Disjoint Set)
Evita ciclos com verificação de componentes
Ideal para grafos esparsos
Disjoint Subsets (Union-Find)
Utilidade: verificar se dois vértices estão no mesmo conjunto
Operações:
find(u): retorna o representante do conjunto de u
union(u, v): une os conjuntos de u e v
Otimizações:
Union by rank
Path compression
Aplicação: algoritmos de Kruskal, detecção de ciclos