Please enable JavaScript.

Coggle requires JavaScript to display documents.

M13 - Coggle Diagram

- - - - A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto V de vértices do gráfico. Em cada iteração, o algoritmo expande a árvore atual de maneira gananciosa, simplesmente anexando é o vértice mais próximo que não está naquela árvore
      - O algoritmo para após todos os vértices do gráfico terem sido incluída na árvore em construção. Como o algoritmo expande uma árvore por exatamente um vértice em cada uma de suas iterações, o número total de tais iterações é n - 1, onde n é o número de vértices no gráfico. A árvore gerada pelo algoritmo é obtido como o conjunto de arestas usado para as expansões da árvore.
- - - - O algoritmo começa classificando as bordas do grafo em ordem não decrescente de
        seus pesos. Então, começando com o subgrafo vazio, ele examina esta lista ordenada, adicionar a próxima borda da lista ao subgrafo atual se tal inclusão não criar um ciclo e simplesmente pular a borda de outra forma.
        
        A floresta inicial consiste em | V | árvores triviais, cada uma compreendendo um único vértice do gráfico. A floresta final consiste em uma única árvore, que é uma árvore de abrangência mínima do gráfico. Em cada iteração, o algoritmo
        pega a próxima aresta (u, v) da lista ordenada de arestas do gráfico, encontra as árvores contendo os vértices uev, e, se essas árvores não forem iguais, as une em uma árvore maior, adicionando a aresta (u, v).
        
        Felizmente, existem algoritmos eficientes para fazer isso, incluindo o crucial
        verifique se dois vértices pertencem à mesma árvore. Eles são chamados de algoritmos de union-find
    - - 1 - Setar(x) cria um set de um elemento {x}. Assume-se que essa operacao precisa ser feita com cada elemento de S apenas uma vez
        2-Achar (x) retorna um subset que contem x
        3- União (x, y) constrói a união dos subconjuntos disjuntos Sx e Sy contendo
        x e y, respectivamente, e adiciona-o à coleção para substituir Sx e Sy, que
        são excluídos dele.
      - Existem duas alternativas principais para implementar essa estrutura de dados.
        A primeira é o quick find que otimiza a eficiência de tempo da operação de localização; o segundo, denominado quick union, otimiza o funcionamento do sindicato.
        
        A Quick find usa uma matriz indexada pelos elementos do conjunto subjacente
        S; os valores da matriz indicam os representantes dos subconjuntos que contêm aqueles
        elementos Cada subconjunto é implementado como uma lista vinculada cujo cabeçalho contém os ponteiros para o primeiro e último elemento da lista junto com o número de elementos
        na lista
        
        No geral o quick find tem uma eficiencia de O(n^2) mas pode ser abaixado se aplicar a técnica de union by size e chega a ficar com O(nlogn)^3 para múltiplas uniões
        
        A Quick union - a segunda alternativa principal para a implementação de disjunção subconjuntos - representa cada subconjunto por uma árvore com raiz. Os nós da árvore contêm os elementos do subconjunto (um por nó), com o elemento da raiz considerado o
        representante do subconjunto, as bordas da árvore são direcionadas dos filhos para seus pais
        
        A eficiência geral desse algoritmo é de O(n) mas caso utilize de union by size e union by weight a eficiencia pode cair para O(logn)