Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algoritmo de Prim, Algoritmo de Kruskal, Algoritmos de Union Find - Coggle…

- - - - Assim, a minimum spanning tree, é a spanning tree de menor peso para um grafo
  - - - Um vértice arbritário do grafo é escolhido para ser raiz da árvore
        
        Depois, é incluso na árvore o vértice não ligado à árvore e adjacente a um vértice da árvore no grafo com ligação de menor peso
        
        O processo acima é repetido até que a árvore contenha todos os vértices do grafo
        
        Para identificar o próximo vértice a ser adicionado, é necessário guardar as informações de ligações dos vértices
        
        Isso pode ser feito guardando em cada vértice do grafo, valores referentes ao vértice da árvore que está mais próximo e o peso da ligação
        
        Além disso, também pode-se separar os vértices dos grafo em duas categorias, fringe e unseen
        
        Fringe são os vértices adjacentes a um vértice da árvore no grafo. Eles são sempre os candidatos a serem adicionados
        
        Unseen ou não-vistos são os vértices não adjacentes a um vértice da árvore. Eles são chamados assim porque são são reconhecidos pelos algoritmo.
        
        Em termos práticos, usaríamos uma lista prioritária para encontrar o próximo vértice
    - - A eficiência do Algoritmo de Prim depende das implementações de grafo e lista prioritária que forem usadas
        
        Sua melhor possibilidade é a versão com um grafo como lista de adjacências e uma heap miníma para lista prioritária
        
        Nela, o algoritmo entra na classe de eficiência não pior que E * log(N), sendo N o número de vértices, e E, o de linhas do grafo
- - - - Se formar, é ignorada, se não, os vértices são inseridos na árvore
      - Determinar se um vértice formaria ou não um ciclo na árvore é um processo não trivial e que aumenta a complexidade do Algoritmo de Kruskal, se comparado com o de Prim
        
        Por isso, torna-se conveniente o uso de uma interpretação diferente para o algoritmo
  - - - Assim, a minimum spanning tree itera sobre a lista de linhas verificando se a linha ligaria duas árvores. Se não, a ligação é inserida na árvore
        
        Para isso, é preciso usar um algoritmo de union find, que determina se dois vértices estão na mesma árvore
    - - A eficiência do algoritmo de Krustal depende do algoritmo usada para ordenar a lista de linhas
        
        Com um bom algoritmo de ordenação, ela pode chegar a não pior que E * log(E), sendo E o número de ligações do grafo
- - - - "quick find" foca em otimizar as operações de busca
        
        Nele, o conjunto de conjuntos é representado como uma array onde os indexes são os valores dos elementos, e o conjunto, como uma lista duplamente ligada
        
        Aqui, a eficiência da busca e da criação de um conjunto de 1 elemento é constante, mas a união é menos eficiente
        
        A ineficiência da união pode ser remediada ligando o menor conjunto ao maior. Isso é chamado union by size
      - "quick union" foca em otimizar as operações de união
        
        Nele, os conjuntos são representados por árvores enraizadas onde os nódulos contém os valores dos elementos e as linhas são direcionadas de pais a filhos
        
        Além disso, as relações de um nódulo a sua raiz é registrada em uma array
        
        Agora, para unir dois conjuntos, basta por a raiz de um como filho de uma folha do outro, uma operação de eficiência temporal constante
        
        A criação de um conjunto de um elemento também tem eficiência constante, mas a operação de busca fica na classe linear
        
        Essa implementação também pode ser melhorada com union by size, sendo o tamanho determinado pelo número de nódulos ou a altura da árvore
        
        2 more items...