Grafos Union find

Prévia do material em texto

Algoritmos e Estruturas 
de Dados II 
 
Union-find 
Gustavo Batista 
Introdução 
Aplicações para union-find: 
n  Dada uma rede de computadores, 
desejamos saber se dois computadores 
estão na mesma rede 
n  Dado um mapa com ferrovias e rodovias, 
queremos saber se existe caminho entre 
duas cidades 
n  Dada uma rede social, queremos saber se 
existe uma cadeia de amigos entre duas 
pessoas 
2 
TAD Union-find 
Disjoint-Set Data Structure (DSDU): é uma 
estrutura de dados que mantém sub-
conjuntos de elementos mutuamente 
exclusivos 
Union-find: é um TAD com as seguintes 
operações sobre a DSDU: 
n  Find(X): diz a qual sub-conjunto X pertence 
n  Union(X, Y): se X e Y pertencem a sub-conjuntos 
diferentes, então os sub-conjuntos são unidos, ou 
nada acontece. 
3 
TAD Union-find 
4 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
Find(2) = verde 
Union(2, 3) 
Find(3) = verde 
Abordagem 1: Quick find 
Para descrever a qual cada sub-
conjunto pertence, vamos utilizar um 
vetor id[]: 
5 
Abordagem 1: Quick find 
Find(X) pode ser implementado em 1 linha e tem 
complexidade O(1): 
No entanto é preciso garantir que ao executar 
Union(1,2) e Union(2,3) todos os 3 elementos 
pertencam ao mesmo sub-conjunto, ou seja, 
id[1] = id[2] = id[3] 
6 
Abordagem 1: Quick find 
Para garantir que os 3 pertencam ao mesmo 
subconjunto basta percorrer todo o vetor alterando 
todos os elementos que tenham id igual ao id[x] para 
id[y]: 
7 
Abordagem 2: Quick union 
Essa abordagem possui o inconveniente da operação 
de union em O(N). 
Podemos tentar deixar o union mais rápido da 
seguinte maneira: 
8 
Abordagem 2: Quick union 
9 
1 2 3 4 5 6 
Abordagem 2: Quick union 
10 
1 
2 3 4 5 6 
Abordagem 2: Quick union 
11 
1 
2 
3 
4 5 6 
Abordagem 2: Quick union 
Para implementar Find basta adotar a convenção de 
que o id do sub-conjunto é o id do nó raiz: 
Mas como fica a complexidade? 
12 
Abordagem 2: Quick union 
Portanto o Find se torna O(N) e 
consequentemente o Union também. 
13 
Abordagem 3: Weighted Quick 
Union 
Para este exemplo com N = 3 tem-se 
duas possibilidades para Union(1, 3) 
14 
1 
2 
3 
1 
2 3 
1 
2 
3 
Union(1,3) Union(1,3) 
Abordagem 3: Weighted Quick 
Union 
A ideia geral é fazer o menor subconjunto 
apontar para o maior 
A consequencia é que a árvore terá altura 
O(log N) 
n  Pense em um sub-conjunto e um nó arbitrário x 
n  Se o sub-conjunto de x é anexado a outro sub-
conjunto, então o tamanho do sub-conjunto unido 
é pelo menor o dobro do sub-conjunto de x 
n  Portanto, o aumento em altura em uma unidade 
leva ao dobro de elementos no pior caso, logo 
log(N) 
15 
Abordagem 3: Weighted Quick 
Union 
16 
x 
x x 
x 
x 
x 
Abordagem 3: Weighted Quick 
Union 
Para saber o tamanho dos subcojuntos vamos definir 
um vetor sz[], que tem tamanho N (um para cada 
elemento) e é inicializado com 1 
17 
Abordagem 4: Weighted Quick 
Union + Path Compression 
Path Compression: usar a execução do Find para 
atualizar e comprimir o caminho do elemento até o 
representante do sub-conjunto. 
18 
Abordagem 4: Weighted Quick 
Union + Path Compression 
Path Compression é obtido por incluir uma única 
linha de código: 
19 
Abordagem 4: Weighted Quick 
Union + Path Compression 
Na prática, ao executar várias vezes o 
Find, a árvore se torna praticamente 
plana, sendo assim, a complexidade do 
Find é O(1). 
Na teoria continua sendo O(log N). 
20 
Exercícios 
Faça a seguinte sequência de unions 
com quick union para 10 elementos: 
n  3-4, 4-9, 8-0, 2-3, 5-6, 5-9, 7-3, 4-8, 6-1 
Faça a mesma sequência de unions com 
quick union e path compression. 
21 
Exercícios 
Faça uma implementação da função 
find que faça compressão de caminho 
forte, ou seja, todo nó intermediário é 
redirecionado para apontar seu 
representante canônico. 
22