União-busca

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de União-Busca)
Ir para: navegação, pesquisa
Ícone de esboço Este artigo sobre estrutura de dados é um esboço. Você pode ajudar a Wikipédia expandindo-o.


Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde maio de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)


União-busca/Disjoint-set
Tipo Árvore
Ano 1964
Inventado por Bernard Galler e Michael John Fischer
Complexidade de Tempo em Notação big O
Algoritimo Caso Médio Pior Caso
Espaço O(n)[1] O(n)[1]
Busca O(α(n))[1] O(α(n))[1]
Merge O(α(n))[1] O(α(n))[1]

Em ciência da computação, uma estrutura de dados união-busca também chamado de estrutura de dados disjoint-set é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos (não sobreposicionados). Ele fornece operações com tempo quase constante (delimitadas pela inversa função de Ackermann) para adicionar novos conjuntos, para mesclar conjuntos existentes e para determinar se os elementos estão no mesmo conjunto. Além de muitos outros usos, os disjoint-sets desempenham um papel fundamental no algoritmo de Kruskal para encontrar a árvore de extensão mínima em um grafo.

Operações[editar | editar código-fonte]

Um algorítmo união-busca é um algoritmo que executa duas operações úteis em tal estrutura de dados:

  • União: união de dois subconjuntos em um único;
  • Busca: determina em qual subconjunto um elemento em particular está. Esta operação também pode ser utilizada para determinar se dois elementos estão em um mesmo subconjunto.

Referências[editar | editar código-fonte]