Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST(Minimun Spanning Tree) - Coggle Diagram
MST(Minimun Spanning Tree)
Definição
Grafos
encontrar o custo mínimo para conectar todas as arestas
encontrar o subconjunto E' de E tal que:
E' = V - 1
soma dos pesos de E' é mínima
se todas as arestas tiverem o mesmo peso, todo grafo é uma MST
para uma árvore geradora de custo T, ela é mínima somente se nenhuma outra árvore tiver um custo menor que T
não direcionado
ponderado
não possui ciclos
somente se for conexo
aplicações
Distribuição de energia em uma área, com o menor custo
Planejamento rodoviário
redes de telecomunicações
planejamento urbano e saneamento
Algoritmo de Prim
algoritmo guloso
expande a subárvore a partir de um vértice V inicial
a cada iteração, anexa o vértice mais próximo
vértice mais próximo
não está na subárvore que esta sendo construída
é o caminho mais curto(aresta de menor peso)
para quando todos os vértices já tiverem sido incluídos
ao visitar o vértice, marca ele como VISITADO
grafos conexos
eficiência
Com lista de adjacência e heap
O((V + E) log (V))
V = vértice
E = arestas
Matrix de adjacência sem heap
O(V²)
grafos ponderados
positivos
negativos
similar a Dijkstra
melhor para grafos densos
Algoritmo de Kruskal
grafos
conexo
ponderado
positivos
negativos
melhor para grafos esparsos
Eficiencia
Com heap
O((V+E)log(V))
Com union find e path comrpession
O(E (log(E)))
algoritmo guloso
escolhe a aresta mais leve possível que não crie ciclos
Funcionamento
Começa com n = V MST´s
cada vértice é uma árvore
a cada iteração escolhe a aresta E com menor peso
Liga 2 árvores diferentes sem formar ciclo (UNION-FIND)
Faz crescer uma 'floresta' até que o grafo se torne conexo
constrói respeitando os critérios de uma MST
floresta é um conjunto de árvores disjuntas
A floresta geradora contém todos os vértice de G
Uma floresta geradora de um grafo G é um subgrafo de G
no início, cada vértice está isolado
vai juntando cada vértice não conectado durante a execução do Kruskal(as árvores vão se unindo)
vértices são adicionados caso eles ainda não pertençam a floresta e somente se ele não formar um ciclo ao ser adicionado(UNION-FIND faz esse teste)
termina quando tudo vira uma única árvore MST
Union find
agrupa elementos em conjuntos disjuntos
verifica se 2 elementos estão no mesmo conjunto
unir conjuntos diferentes
operações principais:
make_set(x)
inicializa o conjunto de x
cada elemento é seu próprio pai
Complexidade O(1)
find(x)
retorna a raiz do conjunto de x
Complexidade O(N)
union(x,y)
une os conjuntos x e y, conectando a raiz dos 2 conjuntos
Complexidade O(N)
raiz = elemento que representa o conjunto
nó mais acima da árvore que representa o conjunto
usado para a implementação de vários algoritmos(incluindo Kruskal)
calcula o número de componentes do grafo
Otimizações
Union by rank ou size
controla como os conjuntos se unem
matem as ávores com pouca profundidade
ao unir 2 conjuntos, coloca a menor árvore embaixo da maior
vetor alt[]
guarda o rank das árvores
compara as alturas no momento da union
Usada em conjunto com o path compression
path compression
a cada operação FIND
plante atalhos no caminho para cada vértice visitado
cada vértice agora vai apontar diretamente para a raiz do conjunto
evita que a árvore tenha que ser visitada em O(N)
Otimiza muito para árvore muito profundas
tempo de busca quase instântaneo
encurta o caminho entre os elementos e suas raizes
obs: os pseudocódigos estão em um docs compartilhado junto, a formatação do coggle fica ruim, não consigo dar shift+enter para identar o código corretamente