segunda-feira, 14 de janeiro de 2013

Conjuntos Disjuntos


A estrutura de dados de conjuntos disjuntos é uma estrutura de dados que mantém eficientemente um conjunto de elementos particionado  em conjuntos disjuntos. Duas operações são importante sobre esta estrutura:

FIND: encontrar o conjunto de um dado elemento
UNION: unificar dois conjuntos


p[x] = representa o líder do conjunto disjuntos
rank[x] = é o limite superior para a altura do nó. O algoritmo constrói implicitamente uma árvore em que as folhas são os líderes de cada conjunto disjunto e todos os "liderados" apontam diretamente ou indiretamente para o líder do conjunto.

Make Set(x)
1) p[x] ← x
2) rank[x] ← 0

Union(x, y)
1) Link(Find Set(x),Find Set(y))

Link(x, y)
1) if rank[x] > rank[y]
2) then p[y] ← x
3) else p[x] ← y
4) if rank[x] = rank[y]
5) then rank[y] ← rank[x] + 1

Find Set(x)
1) if x == p[x]
2) then p[x] ← Find Set(p[x])
3) return p[x]

Heuristicas

Union By Rank: faça a raiz da árvore com menor número de elementos apontar para a raiz da árvore com maior número de elementos. O rank ou ordem é um limite superior para a altura do nó.

Path Compression: durante uma busca faça os nós do caminho apontar para a raiz

Vamos representar o vetor p[x] por uma seta apontando para o líder do conjunto e  rank será representado por um número ao lado do vértice

Operação Make-Set




UNION (1,2)
Union (1,3)
Union(4,5)
Union(1,4)
Note que a união é feita entre os líderes de cada conjunto, ou seja, será executada link(2,5)

Union(3,5)
Observe que o elemento 3 está no mesmo conjunto que o elemento 5. Nesse caso, a heuristica de compressão de caminho entra em ação.


Algumas aplicações:

Problemas:


O código do union-find está neste post.





2 comentários:

Thiago Sena disse...
Este comentário foi removido pelo autor.
Thiago Sena disse...

Como ele faz essa heuristica de compressão de caminho se quando ele for chamar a função find para o elemento 3 e 5, a função link(find(3), find(5)) vai retornar link(5, 5) e não link(3, 5)?