Algoritmos em Grafos
Árvores Geradoras
Prof. André Renato
1º Semestre / 2012
Algoritmos em Grafos

Vamos voltar a falar em árvores:
◦ Como definir a estrutura de dados “árvore”?
◦ Quais os elementos que compõem uma
árvore?
◦ Em relação ao número de filhos de cada nó,
como podem ser as árvores?
Algoritmos em Grafos
Se pensarmos nas árvores como grafos
acíclicos (sem ciclos) não-direcionados,
qual a quantidade de arestas que
podemos ter?
 Qual seria a raiz da árvore?

Algoritmos em Grafos
No processo de confecção de circuitos
eletrônicos, é muito comum precisar
fazer com que diversos pinos (partes do
circuito) sejam eletricamente
equivalentes.
 Isto equivale a dizer que estes pinos
precisam estar conectados entre si,
através de fios.

Algoritmos em Grafos
Deverão ser utilizados n-1 fios, para
conectar n pinos.
 A colocação dos fios deve ser tal que seja
gasta a menor quantidade possível de fios.
 Este problema pode ser modelado através
de grafos.

Algoritmos em Grafos
Os pinos são os vértices;
 As possíveis conexões entre pinos são as
arestas;
 O peso (custo) associado às arestas é a
quantidade de fio necessária para a
ligação;
 Nós desejamos encontrar um
subconjunto acíclico de arestas de forma
que a soma de todos os custos seja a
mínima possível.

Algoritmos em Grafos
O resultado é uma árvore que conecta
todos os vértices, chamada de árvore
geradora, uma vez que ela gera o grafo
G.
 O problema é chamado de Problema da
Árvore Geradora Mínima (AGM), ou
Problema da Árvore Geradora de Custo
Mínimo.

Algoritmos em Grafos

Existem dois algoritmos mundialmente
famosos para este problema;
◦ Prim;
◦ Kruskal;

A utilização de um ou de outro vai
depender de características do grafo,
como sua esparsidade, por exemplo.
Algoritmos em Grafos
Ambos utilizam a estratégia gulosa de
escolher primeiro as arestas de menor
custo possível;
 Em ambos está presente, direta ou
indiretamente, a preocupação de não
formar ciclos com as escolhas realizadas.

Algoritmos em Grafos

Algoritmo de Kruskal:
◦ A idéia por trás deste algoritmo é ordenar
todas as arestas em ordem não-decrescente
de peso;
◦ Escolher as arestas pela ordem, de forma que
possam ser colocadas na resposta sem formar
ciclos.
Algoritmos em Grafos
Colocar as arestas em ordem e
armazená-las em uma lista é um problema
simples de estrutura de dados.
 O problema maior está em saber, de
forma eficiente, se uma aresta, ao ser
colocada na resposta formará ou não um
ciclo.
 Idéias????

Algoritmos em Grafos
Uma solução simples consiste em guardar
um código para cada vértice;
 Inicialmente, cada vértice possui um
código distinto, que pode ser até o
número do próprio vértice;

Algoritmos em Grafos
Se dois vértices são adjacentes na solução
do problema, o código dos dois deverá
ser o mesmo.
 Logo, quando uma aresta (v1,v2) for
testada, ela poderá ser colocada na
resposta se codigo(v1)≠codigo(v2);

Algoritmos em Grafos
Quando a aresta for inserida, todos os
vértices v que tenham codigo(v) = v1
deverão receber o código v2 ou viceversa;
 Um vetor de números inteiros de
tamanho n é suficiente para este
propósito;

Algoritmos em Grafos
Antes de explicitar o pseudo-código do
algoritmo, vamos a um exemplo gráfico;
 As arestas em vermelho fazem parte da
solução final do problema (árvore
geradora mínima);
 As demais estruturas serão atualizadas
conforme as explicações dadas;

Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 1 2 2 4 4 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
2
3
4
5
6
7
8
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 2 2 4 4 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
2
3
4
5
3
7
8
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 2 4 4 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
2
3
4
4
3
7
8
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 4 4 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
2
3
4
4
3
7
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 4 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
2
3
3
3
3
7
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 6 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
3
3
3
3
7
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 7 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
3
3
3
3
7
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 7 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
3
3
3
3
3
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 8 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
3
3
3
3
3
3
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 8 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
1
1
1
1
1
1
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 9 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
1
1
1
1
1
1
9
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Arestas: 10 11 14
Nó
1
2
3
4
5
6
7
8
9
Cod
1
1
1
1
1
1
1
1
1
Algoritmos em Grafos

Pseudo-código Kruskal:
◦ Para cada vértice v:
 codigo(v) := v;
◦ Ordenar as arestas na lista L (não-decrescente);
◦ Retirar a aresta (v1,v2) da frente da lista;
 Se codigo(v1) ≠ codigo(v2) então:
 Inserir a aresta na solução;
 Para cada vértice v:
 Se codigo(v) = codigo(v2) então codigo(v) := codigo(v1)
Algoritmos em Grafos
Qual a complexidade do algoritmo de
Kruskal?
 Para fazer a atualização dos códigos é
possível utilizar uma estrutura de dados
chamada de heaps de Fibonacci.
 Com ela, o processo de atualização dos
códigos diminui a complexidade para
O(lg n);

Algoritmos em Grafos
O algoritmo de Prim monta a árvore
geradora mínima, partindo de um nó
previamente estabelecido;
 Os demais nós vão sendo incorporados
de forma a se conectar com a árvore com
o menor custo possível;

Algoritmos em Grafos
Estes nós que ainda não foram
incorporados, ficam em uma lista
ordenada;
 A ordenação da lista é feita de acordo
com a menor distância que cada vértice
tem para a árvore parcial que está sendo
montada;

Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
3
4
5
6
7
8
9
Dist




0




Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
3
4
6
7
8
9
-
Dist

8

2

7
4

-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
3
6
7
8
9
-
-
Dist

8
7
6
7
4

-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
3
6
7
9
-
-
-
Dist

8
7
2
7
10
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
3
7
9
-
-
-
-
Dist

8
1
7
10
-
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
7
9
-
-
-
-
-
Dist
8
8
7
10
-
-
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
1
2
9
-
-
-
-
-
-
Dist
8
8
9
-
-
-
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
2
9
-
-
-
-
-
-
-
Dist
4
9
-
-
-
-
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
9
-
-
-
-
-
-
-
-
Dist
9
-
-
-
-
-
-
-
-
Algoritmos em Grafos
8
2
4
1
7
5
7
9
2
4
11
4
7
14
9
6
8
10
1
3
2
6
8
Nó
-
-
-
-
-
-
-
-
-
Dist
-
-
-
-
-
-
-
-
-
Algoritmos em Grafos

Pseudo-código do algoritmo de Prim:
◦ Para cada vértice v:
 dist[v] := ;*
◦ dist[r] := 0;
◦ Insere, em uma lista de prioridade L, todos os
vértices de acordo com dist[];
◦ Enquanto L não estiver vazia:
 u := elemento de menor dist[] de L;
 Para todos os vértices v adjacente a u, que estão em L:
 Se w(u,v) < dist[v] então
 dist[v] := w(u,v); //atualizar L*
Algoritmos em Grafos
Complexidade do algoritmo?
 Utilizando heaps de Fibonacci, reduz para
O(E + V lgV)

Algoritmos em Grafos
Os resultados dos algoritmos deverão ter
o mesmo valor, embora possam
apresentar arestas distintas.
 O algoritmo de Prim utiliza a idéia de
escolher um vértice inicial para a geração
da árvore.
 Se o algoritmo for modificado para anotar
a qual predecessor os vértices estão
associados, é possível obter a árvore
geradora de forma mais direta;
