Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's and Kruskal Algorithm - Coggle Diagram
Prim's and Kruskal Algorithm
Prim's Algorithm
dado n pontos, queremos conecta-los de forma que para qualquer par exista um caminho
pratical applications
comunicações
transporte
computadores
redes elétricas
points = vértices
connections = arestas
connection cost = weight
spanning tree
subgráfo sem ciclo com todos os vértices do grafo
minimun spanning tree
com um "weighted graph", é a que somando as aréstas tem o menor peso
constroi uma árvore geradora mínima com uma sequência de subárvores
passo a passo
começa com um vértice arbitrário
a cada iteração adiciona o mas próximo que já não esteja na árvore
quando todos os vértices estiverem na árvore o algoritmo para
labels
nome do vértice mais perto
se não houver = NULL
peso da aresta correspondente
se não houver = infinito
escolhemos o próximo vértice e fazemos duas operações
1°) move u* (vértice escolhido) para a árvore
2°) atualiza os labels de todos os vértices ligados a u*
OBS: a eficiência do algoritmo depende da estrutura usada
best to worst:
adjacency list + min-heap
weight matrix + min heap
weight matrix + unordered array
Kuskal Algorithm
Disjoint Subsets and Union-Find Algorithms
após dividir os elementos ocorre uma sequência de operações
markset
cria um "set" de um elemento
find
retorna o subset contendo "x"
union
une Sy com Sx, adiciona a coleção e deleta Sy e Sx (sozinhos)
Quick find
otimiza a operação "find"
usa um array indexado pelos elementos de s
cada subset é uma linked list contendo
ponteiro para o 1° elemento (representante)
ponteiro para o útimo elemento
número de elementos
OBS: para melhorar a operação de união podemos anexar sempre as listas mais curtas as mais longas
Quick union
otimiza a operação "union"
usa rooted tree, em que as raízes são os representantes
mapeamento com array de ponteiros dos elementos até suas respectivas árvores
OBS: para melhorar a eficiência podemos fazer a operação "union" conectando a raiz da menor árvore na maior
medidas
union by size
quantidade de nós
union by rank
altura
convere se os vértices estão na mesma árvore antes de unir
o algoritmo vê a MST como um subgrafo acíclico de (|v| - 1) arestas
o grafo pode ser desconexo em algumas etapas
passo a passo
ordena as arestas pelo peso
vê se adicionar elas forma algum ciclo
se sim, pula a aresta
todo componente conectado que for gerado é uma árvore (já que não possui ciclos)
se não: adiciona a subárvore
outra interpretação
o algoritmo é uma progressão por uma floresta com todos os vértices de um grafo, mas só algumas arestas
a floresta inicial consiste em |v| árvores triviais (de 1 vértice)
a cada iteração ele acha uma aresta (u,v) e se preciso, une as duas árvores em uma maior