Please enable JavaScript.
Coggle requires JavaScript to display documents.
Minimum-cost spanning tree(MST) - Coggle Diagram
Minimum-cost spanning tree(MST)
Minimum-cost spanning tree
É um subgrafo conectado acíclico de um grafo não orientado conectado (precisa conter todos os vértices), onde este deve possuir o menor peso possível, e esse peso é definido pela soma dos pesos dos arcos que o conectam.
Prim’s algorithm
Constrói uma MST a partir de uma sequência de expansão de subárvores.
A subárvore inicial é composta por um vértice arbitrário do grafo.
A cada interação expandimos a subávore adicionando a ela o vértice mais próximo não contido na mesma (O vértice mais próximo consiste no nó conectado a subávore no qual o peso do seu arco é o menor possível).
O algoritmo utiliza n - 1 interações ( n = número de vértices) e só para quando todos os vértices do grafo foram inserido na subárvore.
Eficiência Temporal
Matriz
Θ(|V|^2)
Lista
Θ(|E| log |V|)
Kruskal’s algorithm
Disjoint subsets
Conjunto S com N elementos particionado em N subconjuntos cada um contendo um elemento diferente do conjunto.
Operações
Find(busca)
Union(união)
Makeset(criação)
Implementações
Quick find
Usa um array indexado pelos elementos do conjunto S para representar os elementos do subconjunto, cada subconjunto é implementado como lista ligada.
Quick union
Utiliza uma raiz enraizada para representar cada subconjuntos, cada nó da árvore é um elemento do subconjunto.
O algoritmo começa ordenando todos os arcos do grafos em ordem crescente em uma lista,
A subárvore inicial é vazia.
A cada interação escaneamos a lista ordenada adicionando o próximo arcos na lista no subávore, se a adição não criar ciclos, caso contrário, pula para o próximo item da lista,
Eficiência Temporal
Θ(|E| log |E|)