Please enable JavaScript.
Coggle requires JavaScript to display documents.
Árvores Geradoras Mínimas - Coggle Diagram
Árvores Geradoras Mínimas
Algoritmo de Prim
Etapas
Iterativamente adiciona aresta de menor peso conectando a árvore a um novo vértice
Repete até incluir todos os vértices
Começa com 1 vértice
Dados auxiliares
Distância mínima até a árvore atual (d[v])
Vértice pai (p[v])
Ideia
Expande a árvore a partir de um vértice inicial
Sempre adiciona o vértice mais próximo não visitado
Complexidade
O(V²) (Matriz + Array)
O(E log V) (Lista + Min-Heap)
Objetivo
Encontrar a árvore geradora mínima (MST) conectando todos os vértices com menor custo
Algoritmo de Kruskal
Etapas
Percorre a lista: se a aresta não forma ciclo, adiciona
Para checar ciclos, usa Union-Find
Ordena arestas por peso crescente
Complexidade
O(E log E) = O(E log V), com sort eficiente + union-find
Ideia
Adiciona uma a uma, evitando ciclos
Usa estrutura de floresta de subconjuntos
Ordena as arestas por peso
Objetivo
Construir MST por arestas, e não por vértices
Sempre pega a menor aresta disponível, sem formar ciclos
Conjuntos Disjuntos e Algoritmos Union-Find
Implementações
Quick Find: find(x) rápido, union lento
Quick Union: usa árvores com ponteiros para pais
Otimizações
Union by size/rank: sempre une o menor no maior
Path compression: durante find(x), encurta caminho apontando direto para a raiz
Operações principais
find(x): retorna representante do conjunto de x
union(x, y): une os conjuntos de x e y
makeset(x): cria conjunto {x}
Eficiência total
Sem otimização: até O(n²)
Com otimizações: quase linear O(n + m·α(n)), onde α(n) é a função inversa de Ackermann (muito lenta de crescer)