Diferentes abordagens para implementação de estruturas de union find com operação de exclusão

Abstract

Um problema recorrente na computação é particionar os nós de um grafo em diferentes conjuntos, utilizando estruturas conhecidas como union-find. Uma implementação padrão dessa estrutura oferece operações para criar um conjunto, procurar a qual conjunto um elemento pertence e unir dois conjuntos. Contudo, para algumas aplicações específicas, é necessário excluir um elemento de um determinado conjunto, o que não é contemplado nas implementações tradicionais. Este trabalho explora e compara duas abordagens distintas para implementar a operação de exclusão de elementos em estruturas union-find. Analisamos o uso de memória, o tempo de execução e a aplicabilidade de cada método, fornecendo uma visão abrangente sobre suas vantagens e desvantagens. Através de experimentos e análise teórica, visamos aprimorar as implementações de union-find, tornando-as mais versáteis para diferentes cenários, usando uma aplicação da Biologia Computacional como estudo de caso.