Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvore Geradora Mínima (MST) - Coggle Diagram

- - - - estrutura para gerenciar conjuntos disjuntos
    - - retorna o representante do conjunto ao qual x pertence
    - - une os conjuntos que contêm x e y
    - - Se find(x) == find(y): mesmo conjunto → formaria ciclo
- - - - criar conjunto de arestas da MST: MST ← ∅
      - para cada vértice v em G:
        
        MAKE-SET(v)
      - ordenar todas as arestas de G por peso crescente
      - para cada aresta (u, v) em G (na ordem crescente de peso):
        
        se FIND(u) ≠ FIND(v):
        
        MST ← MST ∪ {(u, v)} //adiciona uma aresta
        
        UNION(u, v)
      - retornar MST
  - - - para cada vértice v em G:
        
        key[v] ← ∞
        
        parent[v] ← NULL
        
        visitado[v] ← falso
      - key[s] ← 0
      - fila ← Min-Heap com todos os vértices, usando key[] como prioridade
      - enquanto fila não estiver vazia:
        
        u ← extrair vértice com menor key da fila
        
        visitado[u] ← verdadeiro
        
        para cada vizinho v de u:
        
        se v não visitado e peso(u, v) < key[v]:
        
        parent[v] ← u
        
        key[v] ← peso(u, v)
        
        atualizar prioridade de v na fila
      - retornar conjunto de arestas (v, parent[v]) onde parent[v] ≠ NULL