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