Please enable JavaScript.

Coggle requires JavaScript to display documents.

ÁRVORE ABRANGENTE MÍNIMA - Coggle Diagram

- - - - BUSCA RÁPIDA
        
        Prioriza operação de busca (saber a que conjunto/árvore um vértice pertence
        
        Faz uso de um array que armazena no índice correspondente a cada grafo o conjunto a que pertence
        
        Faz também uso de um array de listas ligadas que será responsável pela operação de união
        
        No array de listas ligadas, o ponteiro armazenado no índice correspondente a um vértice só contém uma lista se o vértice for o representante atual de um conjunto
        
        Operação de busca em Θ(1), apenas acessa o primeiro array e checa se os dois vértices contém o mesmo número que representa conjunto
        
        Operação de união anexa um conjunto ao outro, percorrendo todos os seus membros por meio da lista ligada e modificando seu array de pertencimento, deletando a lista ligada no final
        
        União por tamanho melhora a eficiência da união, quando se anexa sempre o menor conjunto ao maior
      - UNIÃO RÁPIDA
        
        Representa cada sub-conjunto por uma árvore de enrraizada
        
        Os nós da árvore contém os elementos do conjunto
        
        Raiz da árvore é considerada o representante do conjunto
        
        Ligações da árvore direcionadas dos filhos aos pais
        
        Prioriza operação de união (atualização dos vértices que pertencem à mesma árvore mínima)
        
        Array de ponteiros mapeia elementos a seus nós da árvore
        
        Operação de união em Θ(1), apenas insere a raiz de uma árvore na raiz de outra
        
        Operação de busca em O(n), percorre uma árvore de seu nódulo à raiz retornando o vértice associado à raiz (representante do conjunto)