Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos MST - Coggle Diagram
Algoritmos MST
Algoritmo de Prim
Complexidade
Com matriz de adjacência: Θ(|V|²)
Com heap e lista de adjacência: Θ((|V| + |E|) log |V|)
Não forma ciclos
Nao precisa odenar arestas
Estratégia: expansão de uma arvore a partir de um vértice
Características gerais
Não forma ciclos
Subgrafo conectado aciclico
Abordagem do algoritmo guloso(greedy)
Aplicações
Redes de computadores
Clustering
Aproximações de soluções para problemas complexos
Subconjuntos Disjuntos
Objetivo: Detectar se dois vértices pertencem ao mesmo componente.
Usado em: Verificação de ciclos no algoritmo de Kruskal.
Funções principais
Find
Union
Implementações
Quick-Find:
find rápido: Θ(1)
union lento: Θ(n)
Otimização: união por tamanho
Quick-Union:
Baseado em árvores.
find: Θ(n) no pior caso
Otimizações
União por tamanho/rank
Compressão de caminho
Algoritmo de Kruskal
Complexidade: Θ(E log E)
Adequado para grafos esparsos.
Estratégia: União de componentes desconexos.
Diferenças em relação ao Prim
Prim cresce uma árvore.
Kruskal une componentes