Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmos de MST - Coggle Diagram

- - - - Inicializar a MST como um conjunto vazio;
        
        Para cada aresta ordenada: Se não forma ciclo, adiciona à MST.
        
        Parar quando MST tiver V - 1 arestas.
  - - - Permite acesso rápido à menor aresta
      - Ordem parcial, não total
- - - - Escolhe qualquer vértice como ponto inicial.
      - Crescimento Gradual:
        
        A cada passo, adiciona uma aresta de menor peso que liga um vértice da árvore (MST parcial) a um vértice fora da árvore.
        
        Critério de Escolha:
        
        Aresta de menor peso entre o conjunto de vértices já incluídos e os ainda não incluídos.
        
        Nunca forma ciclos.
  - - - Adiciona arestas conectadas ao heap
        
        Escolhe menor aresta
        
        Se o destino ainda não está na MST:
        
        adiciona o vértice
        
        adiciona a aresta
        
        insere novas arestas no heap
        
        Repete até incluir todos os vértices
  - - - E = número de arestas
        V = número de vértices
- - - - Find: descobrir qual conjunto um elemento pertence (ou seu representante).
      - Union: unir dois conjuntos diferentes em um só.
  - - - Retorna o representante do conjunto ao qual x pertence.
    - - Une os conjuntos que contêm x e y.
      - Pode usar union by rank ou union by size para manter a árvore balanceada.
  - - - Cada elemento guarda o ID do conjunto ao qual pertence.
        
        Find: tempo constante O(1)
        
        Union: lento O(N), pois precisa atualizar vários IDs
    - - Cada elemento aponta para o pai em uma estrutura de árvore.
        
        Find: segue ponteiros até a raiz
        
        Union: conecta a raiz de um conjunto à raiz de outro
    - - Path Compression: achata a árvore durante o find
        
        Union by Rank ou Union by Size: une árvores menores em maiores
        
        Torna ambas as operações praticamente constantes: O(α(N))
  - - - Garante uma estrutura quase plana com otimizações.