Prim's Algorithim , Kruskal’s Algorithm and Disjoint Subsets and Union-Find Algorithms

Prim's Algorithim

Kruskal Algorithm

Algoritmo Guloso

Analisa uma árvore de abrangência minima

Grafo Conectador Ponderado

Constroi uma arvore de abrangencia minima

Sequencia de subgrafos aciclicos

Classifica

Arestas do Grafo

Ordem não decrescente dos pesos

Começa com Subgrafo Vazio

click to edit

Varre a Sorted List

Adiciona a próxima Aresta da lista ao Subgrafo atual, contanto que um ciclo não seja criado

Exatidão Provada

Repetindo

Etapas essências

Algoritmo de Prim

Interpretação Diferente para esse algoritmo

Operação do algoritmo

Progressão

Atrvés de uma serie de florestas

Contém todos os vértices do grafo e algumas de suas arestas

Algoritmo de Busca e União

Melhora a eficiencia

Com um bom algoritmo de ordenação

Eficiencia de Kruskal

O(|E| log|E|)

Identifica grupo de pontos em conjuntos de dados

classificação

Arqueologia

Biologia

Sociologia

Redes

Construções de melhores soluções

Caixeiro Viajante

Arvore de Abrangência

Representar os pontos

Pelo vertice do grafo

Suas possiveis conexões com as arestas

E os custos com o peso

Problema da árvore geradora minima

Grafo Conectado não direcionado

Subgrafo Aciclico conectado

Contém todos os vertices do grafo

Se tiver peso

arvore gerado minima

Arvore geradora de menor peso

Problema de encontrar uma arvore de brangencia minima para um grafo contectado ponderado

Funcionamento

Constroi uma arvore de abrangencia minima

Sequencia de Subárvores em expansão

Subarvore inicial

Unico vertice selecionado arbitrariamente

Expande a arvore de maneira gananciosa

A cada iteração

Anexa Ela ao vertice mais próxima que não está na arvore

Algoritmo para depois que todos os vértices do grafo foram incluídos na arvore

Sempre produz uma árvore geradora minima

Eficiencia

Depende da Estrutura de Dados

Para a Heap

representar o grafo

Disjoinst Subsets and Union-Find Algorithims

Tipo de dado abstrato

Coleção de subconjuntos disjuntos

Conjunto finito

operações

makeset(s)

find(x)

union(x,y)

cria conjunto de um elemento x

Retorna o subconjunto contendo x

constroi a união dos subconjuntos disjuntos Sx e Sy

Muitas Implementações

usa um elemento de cada um dos subconjuntos como representante dele

Menor Elemento

Qualquer Outro Elemento

Assume-se que o elemento do conjunto é inteiro

formas de implementação

localização rapida

união rapida

otimiza a eficiencia do tempo para localizar

otimiza a eficiencia do tempo para unir

Rooted Tree

Matriz indexada pelo elemento do conjunto subjacente

cada subconjunto é uma lista vinculada