javascript-algorithms

Conjunto Disjuntor (Disjoint Set)

Conjunto Disjuntor

Conjunto Disjuntor é uma estrutura de dados (também chamado de estrutura de dados de union–find ou merge–find) é uma estrutura de dados que rastreia um conjunto de elementos particionados em um número de subconjuntos separados (sem sobreposição). Ele fornece operações de tempo quase constante (limitadas pela função inversa de Ackermann) para adicionar novos conjuntos, para mesclar/fundir conjuntos existentes e para determinar se os elementos estão no mesmo conjunto. Além de muitos outros usos (veja a seção Applications), conjunto disjuntor desempenham um papel fundamental no algoritmo de Kruskal para encontrar a árvore geradora mínima de um gráfico (graph).

disjoint set

MakeSet cria 8 singletons.

disjoint set

Depois de algumas operações de Uniões, alguns conjuntos são agrupados juntos.

Referências