Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo de Prim, Algoritmo de Kruskal - Coggle Diagram

- - - - O peso total é a soma dos pesos das arestas que fazem parte da árvore
- - - - Expande a árvore de forma gulosa
        
        Conecta um vértice da árvore ao vértice mais próximo a ele, mas que não está na árvore
        
        Para depois que todos os vértices do grafo foram incluídos na árvore
  - - - Isso deve ser feito para cada vértice adjacente ao que foi adicionado à arvore
- - - - Um ciclo só vai ser formado quando uma aresta conectar dois vértices de um mesmo componente conexo
      - Todos os componentes conexos dos subgrafos gerados pelo algoritmo são árvores, pois são acíclicos
        
        É possível considerar as operações do algoritmo como uma sequência através de várias florestas
        
        Essas contêm todos os vértices do grafo e algumas de suas arestas
        
        No início, existem \(|V|\) árvores, uma para cada vértice
        
        No final, existe apenas 1 árvore contendo todos os vértices
- - - - Quick find
        
        Otimiza a eficiência temporal da busca
        
        Usa um array cujos valores são os os representantes de cada subconjunto disjunto
        
        União por tamanho
        
        Acrescentar a lista menor à lista maior
        
        Eficiência temporal está em \(O(n\log n + m)\), em que \(n\) é o número de elementos e m é o número de operações de busca
      - Quick union
        
        Otimiza a eficiência temporal da união
        
        Representa cada subconjunto como uma árvore enraizada na qual cada nó representa um elemento do subconjunto
        
        As arestas são dirigidas dos filhos para os pais
        
        A união de subconjuntos também pode ser feita conectando uma árvore menor à raiz de uma árvore maior
        
        Tamanho definido pelo número de nós
        
        União por tamanho
        
        Tamanho definido pela altura da árvore
        
        União pelo rank
        
        Eficiência temporal está em \(O(n+m\log n)\), em que \(n\) é o número de elementos e m é o número de operações de busca