Arvores Abrangentes de Custo MınimoEm ingles, Minimum Spanning Trees (MST)

Fernando Lobo

Algoritmos e Estrutura de Dados

1 / 39

Minimum Spanning Tree

Input: grafo G = (V ,E ) nao orientado, conexo. Cada aresta(u, v) ∈ E tem um peso associado → w(u, v).

Output: Um conjunto de arestas A ⊆ E tal que:

1 A e uma arvore que conecta todos os nos do grafo (A e uma spanningtree), e

2 w(A) =∑

(u,v)∈A w(u, v) e o mınimo possıvel.

Problema tem muitas aplicacoes praticas. Por exemplo, na construcaode uma rede de comunicacoes.

2 / 39

Exemplo de uma MST

Custo: 6 + 5 + 9 + 7 + 15 + 8 + 3 = 53

3 / 39

Propriedades de uma MST

Tem |V | − 1 arestas.

Nao tem ciclos.

Pode nao ser unica.

4 / 39

Algoritmo generico para obter uma MST

Manter um conjunto A de arestas que e sempre um subconjunto dealguma MST.

Inicialmente A = ∅

A cada iteracao acrescentamos uma aresta a A mantendo o invarianteque A continue a ser um subconjunto de uma MST.

5 / 39

Dois algoritmos classicos: Prim e Kruskal

Algoritmo de Prim: Comeca com um no s qualquer e cresce umaarvore A a partir de s. Em cada iteracao, acrescenta o aresta (u, v)de custo mınimo em que um dos extremos pertence a A.

Algoritmo de Kruskal: Comeca com A = ∅. Ordena os arestas dografo por ordem crescente de peso. A cada iteracao acrescenta aaresta (u, v) a A desde que isso nao de origem a um ciclo.

6 / 39

Algoritmo de Prim

Tem semelhancas com BFS e com o algoritmo de Dijkstra.

Inicialmente A = ∅

Mantemos V − A numa fila com prioridade Q.

A chave de cada no na fila indica o custo mınimo de juntar esse no aum qualquer no de A.

Quando o algoritmo termina, a fila Q esta vazia. A MST A e dadapor:

A = {(v , v .π) : v ∈ V − {s}}

7 / 39

Pseudocodigo

MST-Prim(G ,w , s)

for each u ∈ G .Vu.key = ∞u.π = nil

s.key = 0Q = G .Vwhile Q 6= ∅

u = Extract-Min(Q)for each v ∈ G .Adj [u]

if v ∈ Q and w(u, v) < v .keyv .π = uv .key = w(u, v)

8 / 39

Exemplo

9 / 39

Inicializacao

10 / 39

1a iteracao do ciclo while

11 / 39

2a iteracao do ciclo while

12 / 39

3a iteracao do ciclo while

13 / 39

4a iteracao do ciclo while

14 / 39

5a iteracao do ciclo while

15 / 39

6a iteracao do ciclo while

16 / 39

7a iteracao do ciclo while

17 / 39

Complexidade do Algoritmo de Prim

Depende da implementacao da fila com prioridade.

Se implementarmos com um heap binario:

I Inicializacao → Build-Heap → O(V )

I Ciclo while e executado |V | vezes.

I |V | Extract-Mins → O(V lgV )

I No maximo, |E | Decrease-Keys → O(E lgV )

I Total = O(V lgV + E lgV ) = O(E lgV )

A verificacao if v ∈ Q pode ser obtida em tempo constante semantivermos um bit vector com indicacao dos nos que estao em Q.

18 / 39

Algoritmo de Kruskal

Inicialmente A = ∅. No final A sera uma MST.

Ordenamos as arestas do grafo por ordem crescente de peso.

Percorre-se a lista ordenada das arestas, uma a uma, e adicionamos aaresta a A desde que nao produza ciclo.

Ao contrario do algoritmo de Prim, o algoritmo de Kruskal mantemums floresta. Inicialmente a floresta tem |V | arvores, uma para cadano. No final, a floresta so tem uma arvore que e uma MinimumSpanning Tree.

19 / 39

Exemplo: Inicializacao

20 / 39

Iteracao 1

21 / 39

Iteracao 2

22 / 39

Iteracao 3

23 / 39

Iteracao 4

24 / 39

Iteracao 5

25 / 39

Iteracao 6

26 / 39

Iteracao 7, 8, 9, 10

27 / 39

Evolucao da floresta de arvores

Inicializacao

28 / 39

Iteracao 1

29 / 39

Iteracao 2

30 / 39

Iteracao 3

31 / 39

Iteracao 4

32 / 39

Iteracao 5

33 / 39

Iteracao 6

34 / 39

Iteracao 7, 8, 9, 10

35 / 39

Implementacao do Algoritmo de Kruskal

Necessitamos de uma estrutura de dados que permita manterdinamicamente uma floresta de arvores.

Inicialmente temos |V | arvores.

A cada passo do algoritmo juntamos duas arvores e ficamos commenos uma arvore na floresta.

Na realidade, nao e necessario manter explicitamente as arvores.

I Basta manter os nos que cada arvore contem.

I Nota: As arvores sao disjuntas. Um no e elemento de uma e uma soarvore.

36 / 39

Implementacao do Algoritmo de Kruskal

O que necessitamos e de uma estrutura de dados para manter umacolecao S de conjuntos disjuntos.

Essa estrutura de dados tem o nome UNION-FIND (vamos estuda-lana proxima aula).

Suporta estas operacoes: Make-Set(x), Find-Set(x) eUnion(x , y)

I Make-Set(x): cria {x} e acrescenta-o a S .

I Find-Set(x): retorna um identificador do conjunto que contem x .

I Union(x , y): faz a uniao do conjunto que contem x com o conjuntoque contem y e acrescenta-o a S , eliminado os conjuntos originais quecontinham x e y .

37 / 39

Pseudocodigo

MST-Kruskal(G ,w)

A = ∅for each v ∈ G .V

Make-Set(v)sort G .E in ascending order of weight wfor each (u, v) ∈ G .E , taken in ascending order of weight

if Find-Set(u) 6= Find-Set(v)A = A ∪ {(u, v)}Union(u, v)

return A

38 / 39

Complexidade do Algoritmo de Kruskal

Primeiro ciclo for: O(V ) Make-Sets

Ordenar E : O(E lg E )

Segundo ciclo for: O(E ) Find-Sets e UnionsNa realidade so fazemos O(V ) Unions. Porque?

A complexidade vai depender da forma como se implementa aestrutura de dados UNON-FIND.

Mas e possıvel obter uma complexidade de O(E lgV ).Veremos como na proxima aula.

39 / 39