AULA 22
Algoritmos – p.793/823
Conjuntos disjuntos dinâmicos
CLR 22 CLRS 21
Algoritmos – p.794/823
Conjuntos disjuntosSeja S = {S1, S2, . . . , Sn} uma coleção de conjuntosdisjuntos, ou seja,
Si ∩ Sj = ∅para todo i 6= j.
Exemplo de coleção disjunta de conjuntos: componentesconexos de um grafo
PSfrag replacements
G
a b
c d
e f
g
h
i
j
componentes = conjuntos disjuntos de vértices{a, b, c, d} {e, f, g} {h, i} {j}
Algoritmos – p.795/823
Conjuntos disjuntosSeja S = {S1, S2, . . . , Sn} uma coleção de conjuntosdisjuntos, ou seja,
Si ∩ Sj = ∅para todo i 6= j.
Exemplo de coleção disjunta de conjuntos: componentesconexos de um grafo
PSfrag replacements
G
a b
c d
e f
g
h
i
j
componentes = conjuntos disjuntos de vértices{a, b, c, d} {e, f, g} {h, i} {j}
Algoritmos – p.795/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
{a} {b} {c} {d} {e} {f} {g} {h} {i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(b, d) {a} {b, d} {c} {e} {f} {g} {h} {i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(e, g) {a} {b, d} {c} {e, g} {f} {h} {i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(a, c) {a, c} {b, d} {e, g} {f} {h} {i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(h, i) {a, c} {b, d} {e, g} {f} {h, i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(a, b) {a, b, c, d} {e, g} {f} {h, i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(e, f) {a, b, c, d} {e, f, g} {h, i} {j}
Algoritmos – p.796/823
Coleção disjunta dinâmicaConjuntos são modificados ao longo do tempo
Exemplo: grafo dinâmico
PSfrag replacements
G
a b
c d
e f
g
h
i
j
aresta componentes
(b, c) {a, b, c, d} {e, g} {f} {h, i} {j}
Algoritmos – p.796/823
Operações básicas
S coleção de conjuntos disjuntos.
Cada conjunto tem um representante.
MAKESET (x): x é elemento novoS ← S ∪ {x}
UNION (x, y): x e y em conjuntos diferentesS ← S − {Sx, Sy} ∪ {Sx ∪ Sy}x está em Sx e y está em Sy
FINDSET (x): devolve representante do conjunto que contém x
Algoritmos – p.797/823
Connected-Componets
Recebe um grafo G e contrói uma representação doscomponentes conexos.
CONNECTED-COMPONENTS (G)
1 para cada vértice v de G faça2 MAKESET (v)
3 para cada aresta (u, v) de G faça4 se FINDSET (u) 6= FINDSET (v)
5 então UNION (u, v)
Algoritmos – p.798/823
Consumo de tempon := número de vértices do grafom := número de arestas do grafo
linha consumo de todas as execuções da linha
1 = Θ(n)
2 = n × consumo de tempo MAKESET3 = Θ(m)
4 = 2m × consumo de tempo FINDSET5 ≤ n × consumo de tempo UNION
total ≤ Θ(n+m) + n × consumo de tempo MAKESET+2m × consumo de tempo FINDSET+n × consumo de tempo UNION
Algoritmos – p.799/823
Same-Component
Decide se u e v estão no mesmo componente:
SAME-COMPONENT (u, v)
1 se FINDSET (u) = FINDSET (v)
2 então devolva SIM3 senão devolva NÃO
Algoritmos – p.800/823
Algoritmo de KruskalEncontra uma árvore geradora mínima (CLRS 23).
MST-KRUSKAL (G,w) ¤ G conexo
1 A← ∅2 para cada vértice v faça3 MAKESET (v)
4 coloque arestas em ordem crescente de w5 para cada aresta uv em ordem crescente de w faça6 se FINDSET (u) 6= FINDSET (v)
7 então A← A ∪ {uv}8 UNION (u, v)
9 devolva A
“Avô” de todos os algoritmos gulosos.Algoritmos – p.801/823
Conjuntos disjuntos dinâmicos
Seqüência de operações MAKESET, UNION, FINDSET
M M M︸ ︷︷ ︸
n
U F U U F U F F F U F
︸ ︷︷ ︸m
Que estrutura de dados usar?
Compromissos (trade-offs)
Algoritmos – p.802/823
Estrutura lista ligadaPSfrag replacements
G
ab cd
e fghij
cada conjunto tem um representante (início da lista)
cada nó x tem um campo repr
repr [x] é o representante do conjunto que contém x
Algoritmos – p.803/823
Estrutura lista ligada
PSfrag replacements
G
ab cd e fghij
UNION (a, e) : atualiza apontador para o representante.
Algoritmos – p.804/823
Consumo de tempoOperação número de objetos atualizados
MAKESET(x1) 1
MAKESET(x2) 1... 1
MAKESET(xn) 1
UNION(x1, x2) 1
UNION(x2, x3) 2...
...UNION(xn−1, xn) n− 1
total = Θ(n2) = Θ(m2)
Algoritmos – p.805/823
Consumo de tempo
MAKESET Θ(1)
UNION O(n)
FINDSET Θ(1)
Uma seqüência de m operações pode consume tempoΘ(m2) no pior caso.
Consumo de tempo amortizado de cada operação é O(m).
Algoritmos – p.806/823
Melhoramento: weighted-union
PSfrag replacements
G
ab cd e fghij
cada representante armazena o comprimento da lista
a lista menor é concatenada com a maior
Cada objeto x é atualizado ≤ lg n:
cada vez que x é atualizado o tamanho da listadobra.
Algoritmos – p.807/823
Conclusão
Se conjuntos disjuntos são representados atravésde listas ligadas e weighted-union é utilizada, entãouma seqüência de m operações MAKESET, UNIONe FINDSET, sendo que n são MAKESET, consome
tempo O(m+ n lg n).
Algoritmos – p.808/823
Estrutura disjoint-set forest
PSfrag replacements
G
a b
c d
e f
g
h
i
j
cada conjunto tem uma raiz , que é o seu representate
cada nó x tem um pai
pai [x] = x se e só se x é uma raiz
PSfrag replacements
a
b
c
d
e
fg
h
i
j
cada conjunto tem uma raiz
cada nó x tem um pai
pai [x] = x se e só se x é uma raiz
Algoritmos – p.809/823
Estrutura disjoint-set forestPSfrag replacements
a
b
c
d
e
fg
h
i
j
cada conjunto tem uma raiz
cada nó x tem um pai
pai [x] = x se e só se x é uma raiz
Algoritmos – p.809/823
MakeSet0 e FindSet0
PSfrag replacements
a
b
c
d
e
fg
h
i
j
MAKESET0 (x)
1 pai[x]← x
FINDSET0 (x)
1 enquanto pai [x] 6= x faça2 x← pai [x]
3 devolva x
Algoritmos – p.810/823
FindSet1
PSfrag replacements
a
b
c
d
e
fg
h
i
j
FINDSET1 (x)
1 se pai [x] = x
2 então devolva x
3 senão devolva FINDSET1 (pai [x])
Algoritmos – p.811/823
Union0
PSfrag replacements
a
b
c
d
e
fg
h
i
j
UNION0 (x, y)
1 x′ ← FINDSET0 (x)
2 y′ ← FINDSET0 (y)
3 pai [y′]← x′
Algoritmos – p.812/823
Union0
PSfrag replacements
a
b
c
d e
fg
h
i
jx′
y′
UNION0 (a, f)
UNION0 (x, y)
1 x′ ← FINDSET0 (x)
2 y′ ← FINDSET0 (y)
3 pai [y′]← x′
Algoritmos – p.812/823
Union0
PSfrag replacements
a
b
c
d e
fg
h
i
jx′
y′
UNION0 (a, f)
UNION0 (x, y)
1 x′ ← FINDSET0 (x)
2 y′ ← FINDSET0 (y)
3 pai [y′]← x′
Algoritmos – p.812/823
MakeSet0, Union0 e FindSet1
MAKESET0 (x)
1 pai[x]← x
UNION0 (x, y)
1 x′ ← FINDSET0 (x)
2 y′ ← FINDSET0 (y)
3 pai [y′]← x′
FINDSET1 (x)
1 se pai [x] = x
2 então devolva x
3 senão devolva FINDSET1 (pai [x])
Algoritmos – p.813/823
Consumo de tempo
MAKESET0 Θ(1)
UNION0 O(n)
FINDSET0 O(n)
M M M︸ ︷︷ ︸
n
U F U U F U F F F U F
︸ ︷︷ ︸m
Custo total da seqüência:nΘ(1) + nO(n) +mO(n) = O(mn)
Algoritmos – p.814/823
Melhoramento 1: union by rank
x y
PSfrag replacements
1
2
0
0
1
00
1
0
0
rank [x] = posto do nó x MAKESET (x)
1 pai [x]← x
2 rank [x]← 0
Algoritmos – p.815/823
Melhoramento 1: union by rank
PSfrag replacements
1
2
0
0 1
00
1
0
0x
y
UNION (x, y)
rank [x] = posto do nó x MAKESET (x)
1 pai [x]← x
2 rank [x]← 0
Algoritmos – p.816/823
Melhoramento 1: union by rank
PSfrag replacements
1
2
0
0 1
00
1
0
0x
y
UNION (x, y)
rank [x] = posto do nó x MAKESET (x)
1 pai [x]← x
2 rank [x]← 0
Algoritmos – p.817/823
Melhoramento 1: union by rank
PSfrag replacements
rank [x]
rank [x]
rank [x]
rank [y]
rank [y]
rank [y]
rank [y]
rank [x] + 1
>
=
⇒
⇒
Algoritmos – p.818/823
Melhoramento 1: union by rank
UNION (x, y) ¤ com “union by rank”
1 x′ ← FINDSET (x)
2 y′ ← FINDSET (y) ¤ supõe que x′ 6= y′
3 se rank [x′] > rank [y′]
4 então pai [y′]← x′
5 senão pai [x′]← y′
6 se rank [x′] = rank [y′]7 então rank [y]← rank[y] + 1
Algoritmos – p.819/823
Melhoramento 1: estrutura
rank [x] ≤ rank [pai [x]] para cada nó x
rank [x] = rank [pai [x]] se e só se x é raiz
rank [pai [x]] é uma função não-descrente do tempo
número de nós de uma árvore de raiz x é ≥ 2rank [x].
número de nós de posto k é ≤ n/2k.
altura(x) = rank [x] ≤ lg n para cada nó x
altura(x) := comprimento do mais longo caminhoque vai de x até uma folha
Algoritmos – p.820/823
Melhoramento 1: custoSeqüência de operações MAKESET, UNION, FINDSET
M M M︸ ︷︷ ︸
n
U F U U F U F F F U F
︸ ︷︷ ︸m
altura(x) ≤ lg n para cada nó x
Consumos de tempo: MAKESET Θ(1)
UNION O(lg n)
FINDSET O(lg n)
Consumo de tempo total da seqüência: O(m lg n)
Algoritmos – p.821/823
Melhoramento 2: path compression
PSfrag replacementsx
b
c
d
e
FINDSET(x)
PSfrag replacementsa b c d
e
FINDSET(x)
Algoritmos – p.822/823
Melhoramento 2: path compression
PSfrag replacementsa b c d
e
FINDSET(x)
Algoritmos – p.822/823
Melhoramento 2: path compression
FINDSET (x) ¤ com “path compression”1 se x 6= pai [x]2 então pai [x]← FINDSET (pai [x])3 devolva pai [x]
rank [x] ≤ rank [pai [x]] para cada nó x
rank [x] = rank [pai [x]] se e só se x é raiz
rank [pai [x]] é uma função não-descrente do tempo
número de nós de uma árvore de raiz x é ≥ 2rank [x].
número de nós de posto k é ≤ n/2k.
altura(x)≤ rank [x] ≤ lg n para cada nó x
Algoritmos – p.823/823