apresentacao-Kruskal

5/17/2018 apresentacao-Kruskal - slidepdf.com

http://slidepdf.com/reader/full/apresentacao-kruskal 1/27

ALGORITMO DE KRUSKALAlgoritmo polinomial para geração

de uma Árvore Geradora Mínima

de um grafo conexo

Hilio HolzRamon M. Ramos

Professora: Maria Claudia Silva Boeres

Teoria dos GrafosTrabalho Computacional



Hilio Holz e Ramon M. RamoAlgoritmo de Kruskal

Agenda

1. Árvores, Árvores Geradoras, Árvores Geradoras Mínimas eseus pesos

2. O problema da Árvore Geradora Mínima

3. O algoritmo de Kruskal4. Estruturas de dados utilizadas

5. Implementações realizadas

6. Complexidade do algoritmo

7. Resultados obtidos

8. Conclusão




Árvore

O que é?Na teoria dos grafos, uma árvore nada mais é do que um tipo especialde grafo:

Uma árvore Um grafo comum com ciclos

Árvores são grafos em que não existem ciclos!




Árvore Geradora

O que é?Uma árvore é dita geradora se ela interliga (direta ou indiretamente)todos os nós do grafo.




Árvore Geradora Mínima – AGM

O que é?Uma Árvore Geradora Mínima - AGM, ou Minimum Spanning Tree - MST ,de um grafo com pesos nas arestas (grafo valorado) é qualquer árvoregeradora do grafo que tenha peso mínimo.

Vale frisar..

Localizar uma AGM só é possível em grafos valorados, ou seja, compesos nas arestas.




Peso total de uma AGM

O que é peso?

Peso é o valor dado a cada aresta, podendo representar qualquer valorem um problema real, como custo, fluxo, confiabilidade, etc.

Peso total da árvore geradora: 1+2+4+6+12 = 25

Como calcular o peso total?

O peso total de uma AGM é dado pela soma dos pesos das arestas daárvore.


http://slidepdf.com/reader/full/apresentacao-kruskal 7/27Hilio Holz e Ramon M. RamoAlgoritmo de Kruskal

O problema da AGM

O problema da Árvore Geradora Mínima – AGM consiste em encontrar, dado um grafo

com arestas valoradas, uma estrutura de conexão (árvore) em que todos os nós(geradora) se conectem (direta ou indiretamente) uns aos outros.

Essa estrutura deve possuir o menor peso possível, onde o peso é dado pela soma dospesos das arestas escolhidas (mínima).

Como resolver?

formar todas as árvores geradoras possíveis e escolher a de menor peso• Opção 1 – Difícil!

O matemático Arthur Caley provou que um grafo com N nós possui NN-2

árvores geradoras diferentes.

N=4, 16 árvores N=6, 1.296 árvores N=10, 100.000.000 árvores

Apenas 1 árvore mínima

Usar um algoritmo específico para esta tarefa...

• Opção 2 – Melhor



Algoritmos possíveis de AGM

Há quatro possibilidades conhecidas

Algoritmo de Kruskal.

Algoritmo de Prim.

Esta apresentação se limita a demonstrar o comportamento do

Algoritmo de Kruskal

Algoritmo Reverse-Delete.

Algoritmo de Borůvka.



O algoritmo de Kruskal

O que é Floresta Geradora Mínima?

Objetivo

Resolver o problema de AGM para grafos conexos.

Para grafos desconexos encontra a Floresta Geradora Mínima.

Uma Floresta Geradora Mínima é composta pelo conjunto de árvores

geradoras mínimas de cada componente conexo.

É o mesmo princípio das AGM só que para grafos desconexos.

História

Este algoritmo apareceu pela primeira vez no jornal Proceedings of the

American Mathematical Society , em 1956, e foi escrito por Joseph BernardKruskal, Jr.



Funcionamento

1. Lê todas as arestas

2. Ordena em ordem crescente

3. Seleciona cada aresta na ordem

1. Verifica:

1. Se forma ciclo, descarta

2. Senão adiciona à arvore



Programa exemplo

Clicar na figura para abrir o programa...



Estrutura de dados

Matriz de Adjacência com pesos

Lista de Arestas

Estruturas de dados utilizadas

Algoritmo implementado utilizando Conjuntos Disjuntos



Matriz de Adjacência

• Arestas nulas representadas com 999

• Alocado somente metade da matriz

• Sem ordenação!

• Não façam isso em casa!



Lista de Arestas

• Não representa arestas inexistentes

• Não consegue representar grafos desconexos

1 2

3

5

4

5

47

2

10

V1 : 1V2 : 2Custo : 5

V1 : 1V2 : 5Custo : 7

V1 : 1V2 : 3Custo : 2

V1 : 3V2 : 2Custo : 4

V1 : 3V2 : 5Custo : 10



Conjuntos Disjuntos

• Conjuntos de objetos conectados

• Objetos

• Conjuntos Disjuntos

• Find

• Union



Conjuntos Disjuntos - Quick Find

• Estrutura de Dados• Vetor de inteiros id[ ] de tamanho N

• Dois vértices são de mesmo conjunto se tem o mesmo id.

• Find: Retornar o id do nó

• Union: Para mesclar conjuntos contendo p e q, muda-se todas as

entradas com id[p] para id[q]



Conjuntos Disjuntos - Quick Union

• Estrutura de Dados• Vetor de inteiros id[ ] de tamanho N

• id[i] é o pai de i

• Find: Procurar recursivamente até id[i] =i

• Union: mudar o id da raiz de

um dos conjuntos



Heurística 1 - União por Ordenação

•

Union: A raiz de menor ordem aponta para a raiz de maiorordem.

•

ObjetivoEvitar árvores compridas.



Heurística 2 - Compressão de Caminho

• Find: Fazer cada nó no caminho apontar diretamente para a raiz.



Implementação – Complexidade

Estrutura Conjuntos Make Sets Ordenação Find's + Union's

Matriz Quick-Find O(V) O(n3) O(n+Lg n)

Lista

Quick-Find O(V) O(E Lg E) O(n+Lg n)

Quick-Union O(V) O(E Lg E) O(n+Lg n)

QU+heurísticas O(V) O(E Lg E) O(n)

•Make Sets

•Ordenação

•Find's + Union's



Implementação

• Linguagem• C

• Testes

• Grafos

Esparsos

Densos

Completos

• Número de Vértices variando de 50 a 2000 (de 50 em 50)



Resultados – Grafos Esparsos



Resultados – Grafos Densos




Resultados – Grafos Completos




Exemplo

• Ex:Problema realmente grande

• 109 vértices e 1010 arestas

• Aplicação das heurísticas reduz o tempo de 3000 anos para 1

minuto em relação ao Quick-Find

Fonte: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf




Conclusão

• Ordenação tem efeito muito importante

• 'Quick Union + heurísticas' é implementação assintoticamentemais rápida conhecida

• Bons Algoritmos tornam as soluções possíveis



Obrigado!

Dúvidas / Perguntas?

Documents

apresentacao-Kruskal