Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo Prim, Algoritmo Kruskal - Coggle Diagram

- - - - Marginais (Fringe)
        
        Não estão na árvore mas são adjancentes a pelo menos um vértice dela
        
        Candidatos a serem selecionados para ser o próximo vértice a entrar
      - Invisíveis (Unseen)
        
        Todos os outros vértices do grafo
- - - - Problema da spanning tree mínima
        
        Achar a spanning tree mínima para um dado grafo ponderado e conectado
- - - - Alternativa
        
        Uso do Algoritmo Prim
        
        Constrói uma spanning tree mínima expandindo subárvores sequencialmente
        
        Subárvore Inicial
        
        Vértice único e arbitrário escolhido do conjunto V de vértices do grafo
        
        A cada iteração o algoritmo expande a árvore anexando o vértice mais próximo que não está naquela árvore
        
        O algoritmo para após todos os vértices terem sido incluídos na árvore em construção
        
        n-1 iterações
        
        n= número de vértices do grafo
- - - - Θ(|V^2|)
      - Em cada iteração (|V|-1) iterações o array da fila de priordade é percorrido para excluir o mínimo e atualizar as prioridades dos demais vértices
    - - O(|E|log|V|)
        
        |V|-1 deleções do menor elemento e faz |E| verificações de possíveis mudanças nas prioridades
        
        Cada operação está em O(log|V|) e o tempo de execução da implemetação está em (|V|-1+E)O(log|V|)
- - - - Retorna subconjunto contendo x
    - - Constrói a união dos subconjuntos disjuntos Sx e Sy contendo x,y e o adiciona a coleção para substituir Sx e Sy em sua forma individual (desunida), que são excluídos
    - - Cria um conjunto de 1(um) elemento
  - - - Otimiza a operação de união
      - Representa cada conjunto por uma árvore enraizada
        
        Cada nó contém um elemento do subconjunto e a raiz é o representante
      - Implementação makeset(x)
        
        Criação de nó único
        
        Θ(1)
        
        Inicialização de n subconjuntos
        
        Θ(n)
      - União implementada anexando a raiz da árvore de y à raiz da árvore de x e deletando a árvore de y
        
        O ponteiro para a raiz de y torna-se nulo
        
        Eficiência temporal
        
        Θ(1)
      - find(x)
        
        Realizado seguindo os ponteiros do nó que contém x
        
        Eficiência de um único find (x)
        
        Θ(n)
        
        Uma árvore representando um conjunto pode degenerar numa lista com n nós
      - Melhoria
        
        Executar união anexando uma árvore menor à raiz de uma árvore maior
        
        Union by rank (União por posto)
        
        Altura de uma árvore é logarítmica em função da quantidade de nós
        
        Busca em O(log n)
      - Eficiência temporal de uma sequência de n-1 uniões e m buscas está em O(n+ mlogn)
        
        Melhoria de eficiência
        
        Combinação da Quick Union com path compression (compressão de caminho)
    - - Otimiza a eficiência de tempo da busca
      - Usa matriz indexada pelos elementos do conjunto subjacente de S
      - Cada subconjunto é implementado como uma lista ligada
        
        O header aponta para o primeiro e último elemento da lista
      - Os valores da matriz indicam os representantes dos subconjuntos
      - makeset(x)
        
        Atribuição de elemento correspondente na matriz representativa e inicialização de lista ligada correspondente em um único nó com o valor x
        
        Eficiência
        
        Busca
        
        Θ(1)
        
        União-union(x,y)
        
        Leva mais tempo
        
        Solução simples
        
        Union by size (União por tamanho)
        
        Anexação de listas (anexar uma lista mais curta numa mais longa)
        
        Embora não melhore a eficiência do pior caso de uma única aplicação, o pior caso de qualquer sequência acaba sendo
        O(n log n)
        
        Eficiência temporal de no máximo n-1 uniões
        
        1 more item...
        
        Anexação da lista do subconjunto representado por y ao final da lista do subconjunto representado por x
        
        Θ(n^2)
        
        Lento
        
        Inicialização de n subconjuntos
        
        Θ(n)
- - - - Pode haver subgrafos não conectados
    - - Não possui ciclos
    - - Floresta Inicial
        
        |V| árvores com único vértice
      - Floresta Final
        
        Única árvore (minimum spanning tree)
    - - Algoritmos verificam se 2 vértices pertencem a mesma árvore (union-find)
      - Com um union-find eficiente o tempo de execução será dominado pelo tempo necessário para classificar os pesos das arestas de um grafo
        
        O(|E|log|E|)
        
        Eficiência temporal do algoritmo de Kruskal