Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 14 - Coggle Diagram

- - - - Em seguida, o algoritmo faz esse mesmo processo de verificação, não só para os vértices adjecentes a u, mas também os adjecentes a v (ou seja, para todos os vértices adjecentes à árvore)
        
        O algoritmo então escolhe seguir pelo caminho de menor peso, seja o outro vértice, w, adjecente a v ou u
        
        E assim o código segue até que todos os vértices do grafo estejam inclusos na árvore de abrangência mínima
        
        Nesse caso, por exemplo, o algoritmo iria verificar qual caminho que liga um vértice adjecente a v ou u ou w possui o menor peso
        
        O conjunto desses vértices adjecentes à árvore é chamado de "borda"
      - A menos que a aresta seja um laço que ligue v com v
- - - - Subconjuntos Disjuntos
        
        A ADT do tipo subconjunto disjunto deve possuir as seguintes funções:
        
        makeset(x): Vai criar um conjunto {x}, que só deverá possuir 1 elemento
        
        find(x): Retorna um subconjunto que contém x
        
        union(x, y): Pega os subconjuntos disjuntos Sx e Sy, que contém x e y, respectivamente, e junta os dois dentro da lista
        
        Implementação
        
        Quick-find
        
        Prioriza eficiência temporal e a operação de procura (find(x))
        
        Usa uma array, onde os valores indicam os representantes dos subconjuntos contendo aqueles
        elementos (esses sendo os índices da array)
        
        Cada subconjunto é implementado por uma lista ligada, onde o header aponta para o primeiro e para o último elemento da lista; além de possuir o tamanho da lista
        
        Eficiência
        
        makeset(x): Θ(n)
        
        find(x): Θ(1)
        
        union(x, y): Θ(n)
        
        Quick-union
        
        Prioriza a operação de união dos subconjuntos (union(x, y))
        
        Cada subconjunto é representado por uma árvore enraizada, onde a raiz é o elemento representativo do subconjunto
        
        Eficiência
        
        makeset(x): Θ(n)
        
        find(x): Θ(n)
        
        union(x, y): Θ(1)
      - O algoritmo então vai unificando o menor subconjunto disjunto da lista, com o conjunto de arestas da árvore (Et), contanto que sua adição não forme um ciclo dentro do subgrafo definido por Et
        
        O conjunto da árvore (Et) é inicialmente vazio
        
        Isso se repete até que seja verificado que todos os vértices do grafo foram incluídos em Et