UNIVERSIDADE CATÓLICA DE PELOTASESCOLA DE INFORMÁTICA

MESTRADO EM CIÊNCIA DA COMPUTAÇÃO

Disciplina:Estruturas de Dados

Aluno:Christiano Otero Avila

Prof. Dr. Paulo Roberto Gomes Luzzardi

ÁRVORES DE EXPANSÃO MÍNIMA

SumárioSumário

Introdução

Termo em Inglês e Sinônimos

Aplicações

Conceito

Construção passo-a-passo

Algoritmos

Exercícios

Animações

Bibliografia

IntroduçãoIntrodução

Termo em Inglês e SinônimosTermo em Inglês e Sinônimos

Termo em inglês:• Minimum Spanning Tree (MST)

Alguns sinônimos encontrados:• Árvores de Expansão Mínima• Árvores Geradora Mínima• Árvores de Cobertura Mínima• Árvores Espalhadas Mínimas

AplicaçõesAplicações

Projetos de redes de telecomunicações:•Redes de computadores•Redes de fibra ótica•Redes de telefonia•Redes de televisão a cabo

Projetos na área de transportes:•Rodovias, ferrovias, gasoduto (ops....)•Irrigação – “transporte de água”•Logística (distribuição)

Projetos de redes de distr. de energia

Mineração de dados em clustering

AplicaçõesAplicações

Sistemas de Informações Geográficas:

ConceitoConceito

Árvore que interliga todos os vértices do grafo utilizando arestas com um custo total mínimo

ConceitoConceito

Dado um grafo não dirigido ponderado G, desejamos encontrar uma árvore T que contenha todos os vértices de G e minimize sua soma.

Construção passo-a-passoConstrução passo-a-passo

ConceitoConceito

Construção passo-a-passoConstrução passo-a-passo

Construção passo-a-passoConstrução passo-a-passo

Construção passo-a-passoConstrução passo-a-passo

Construção passo-a-passoConstrução passo-a-passo

Construção passo-a-passoConstrução passo-a-passo

AlgoritmosAlgoritmos

- Algoritmo de Prim - Algoritmo de Kruskal- Algoritmo de Boruvka

Algoritmos - PrimAlgoritmos - Prim

O célebre algoritmo de Prim resolve o problema da árvore geradora de peso mínimo num grafo simétrico com função-peso simétrica. O algoritmo foi inventado por R.C. Prim (Bell Systems Techncal Journal, 1957).  No início de cada iteração temos dois tipos de vértices, os pretos e os brancos, e uma árvore com raiz r que "cobre" o conjunto dos vértices pretos. O algoritmo tem um caráter guloso:  cada iteração acrescenta à árvore o arco mais leve dentre os que ligam um vértice preto a um vértice branco.

Algoritmos - PrimAlgoritmos - Prim

A implementação a seguir supõe que os vértices do grafo são 1, 2, … . , n e devolve um vetor de predecessores pai que representa uma r-árvore geradora de peso mínimo.  O algoritmo usa uma "fila" de arcos que contém todos os arcos com ponta inicial preta e ponta final branca. Os detalhes de implementação da fila ficam por conta da imaginação do leitor, mas tudo se passa como se os arcos estivessem na fila sempre em ordem crescente de f. Cada arco é representado como um par ordenado de vértices.

Algoritmos - PrimAlgoritmos - Prim

Animação:http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/PrimApp.shtml?demo6

Algoritmos - KruskalAlgoritmos - Kruskal

Animação:http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/KruskalApp.shtml?demo4

AlgoritmosAlgoritmos

Algoritmo de Boruvka • Também conhecido como Baruvka• A idéia geral desse algoritmo consiste em começar por ligar cada vértice ao seu vizinho mais próximo, criando, no máximo, V/2 árvores. Depois, ligar cada árvore à outra árvore que lhe estiver mais próxima, até que todos os vértices do grafo estejam inseridos na árvore.

Algoritmos - BoruvkaAlgoritmos - Boruvka

• O algoritmo de Boruvka compreende os seguintes passos:1. Para cada vértice escolher o seu arco com peso mínimo. Deste passo poderão resultar vários subgrafos.2. Caso o passo 1 dê origem a grafos não conectados, considere cada subgrafo gerado no passo anterior como um vértice do grafo final. Para cada um dos subgrafos gerados execute-se de novo o passo 1.3. Parar quando todos os vértices estiverem conectados entre si formando assim a AGM/MST.

Algoritmos - BoruvkaAlgoritmos - Boruvka

Algoritmos - BoruvkaAlgoritmos - Boruvka

Exercícios Exercícios

• Pretende-se construir novas estradas de modo que 5 cidades (A,B,C,E e E) fiquem ligadas. Os custos de construção das estradas são os indicados na tabela. Informe o valor da árvore geradora mínima.

Exercícios Exercícios

• Dica – construir o grafo

Animações Animações

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml

http://students.ceid.upatras.gr/~papagel/project/prim.htm

http://www.cs.man.ac.uk/~graham/cs2022/greedy/index.html

Bibliografia Bibliografia

• Goodrich, Michael T; Projeto de Algoritmos: Fundamentos análise e exemplos da Internet; Bookman, 2004.• Sampaio, Rudini; Yanasse, Horácio; Estudo e Implementação de Algoritmos de Roteamento sobre Grafos em um Sistema de Informações Geográficas;UFLA,INPE.• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. Introduction to Algoritms; MIT Press, 1999.

UNIVERSIDADE CATÓLICA DE PELOTASESCOLA DE INFORMÁTICA

MESTRADO EM CIÊNCIA DA COMPUTAÇÃO

Disciplina:Estruturas de Dados

Aluno:Christiano Otero Avila

Prof. Dr. Paulo Roberto Gomes Luzzardi