Please enable JavaScript.

Coggle requires JavaScript to display documents.

M14, Kruskal’s algorithm, Prim’s algorithm, Disjoint Subsets and Union…

- - - - Definição
        
        Uma árvore geradora de um grafo conectado não direcionado é seu subgrafo acíclico conectado (ou seja, uma árvore) que contém todos os vértices do grafo.
        
        Se tal gráfico tiver pesos atribuídos às suas arestas, uma árvore geradora mínima é sua árvore geradora de menor peso, onde o peso de uma árvore é definido como a soma dos pesos em todas as suas arestas.
        
        O problema da árvore geradora mínima é o problema de encontrar uma árvore geradora mínima para um determinado grafo conectado ponderado.
      - Aplicações
        
        Tem sido usado para fins de classificação em arqueologia, biologia, sociologia e outras ciências.
        
        Tem aplicações diretas no projeto de todos os tipos de redes – incluindo comunicação, informática, transporte e elétrica – fornecendo a maneira mais barata de obter conectividade.
- - - - Podemos considerar as operações do algoritmo como uma progressão através de uma série de florestas contendo todos os vértices de um determinado grafo e algumas de suas arestas.
        
        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 é a árvore geradora mínima do grafo.
        
        A cada interação, o algoritmo pega a próxima aresta (u, v) da lista ordenada de arestas do grafo, encontra as árvores contendo os vértices u e v e, se essas árvores não forem iguais, as une em uma árvore maior. adicionando a aresta (u, v).
- - - - A franja contém apenas os vértices que não estão na árvore, mas são adjacentes a pelo menos um vértice da árvore. Estes são os candidatos a partir dos quais o próximo vértice da árvore é selecionado.
    - - Os vértices invisíveis são todos os outros vértices do gráfico, chamados de “invisíveis” porque ainda não foram afetados pelo algoritmo
  - - - Vt => conjunto de vértices da árvore || v0 => vértice qualquer
      - Et = NULL
        
        Et = conjunto de arestas da árvore
        
        for (i = 1; i <= |V| - 1)
        
        V => conjunto de vértices do grafo
        
        Encontrar a aresta e com menor peso que liga o vértice v ao um vértice adjacente u
        
        Adicionar o vértice u ao conjunto Vt e remover do conjunto V
        
        Adicionar a aresta e ao conjunto Et
- - - - O algoritmo para depois que todos os vértices do gráfico foram incluídos na árvore sendo construído.
      - Por vértice mais próximo é o vértice que não está na árvore conectado a um vértice na árvore por uma aresta de menor peso. Os empates podem ser quebrados arbitrariamente.
      - Como o algoritmo expande uma árvore exatamente em um vértice em cada uma de suas iterações
        
        n - 1 interações, n == número de vértices
- - - - Fila de prioridade por min-heap
        
        O(|E|log|V|)
    - - Fila de prioridade por array não ordenado
        
        Θ(|V|²)
      - Fila de prioridade por min-heap
        
        O(log n)
- - - - ADT
        
        Existem duas alternativas principais para implementar esta estrutura de dados.
        
        Quick Union(união rápida) => otimiza o funcionamento da união.
        
        representa cada subconjunto por uma rooted tree
        
        Os nós da árvore contêm os elementos do subconjunto (um por nó), sendo o elemento da raiz considerado o representante do subconjunto;
        
        as bordas da árvore são direcionadas dos filhos para os pais
        
        Além disso, é mantido um mapeamento dos elementos do conjunto para seus nós de árvore – implementado, digamos, como uma matriz de ponteiros.
        
        makeset(x) requer a criação de uma árvore de nó único
        
        Eficiência makeset e union => Θ(n)
        
        union(x, y) é implementada anexando a raiz da árvore y à raiz da árvore x (e excluindo a árvore y da coleção, tornando o ponteiro para sua raiz nulo)
        
        1 more item...
        
        Quick Find(busca rápida) => otimiza a eficiência de tempo da operação de busca;
        
        matriz indexada pelos elementos do conjunto subjacente S; os valores da matriz indicam os representantes dos subconjuntos que contêm esses elementos. Cada subconjunto é implementado como uma lista vinculada cujo cabeçalho contém os ponteiros para o primeiro e o último elemento da lista junto com o número de elementos na lista
        
        a implementação de makeset(x) requer a atribuição do elemento correspondente na matriz representativa a x e a inicialização da lista vinculada correspondente a um único nó com o valor x.
        
        Eficiência makeset e find => Θ(n)
        
        A execução de union(x, y) leva mais tempo. Uma solução simples seria simplesmente anexar a lista de y ao final da lista de x, atualizar as informações sobre seu representante para todos os elementos da lista de y e, em seguida, excluir a lista de y da coleção.
        
        2 more items...
      - makeset(x) cria um conjunto de um elemento {x}. Supõe-se que esta operação pode ser aplicada a cada um dos elementos do conjunto S apenas uma vez.
      - find(x) retorna um subconjunto contendo x.
      - union(x, y) constrói a união dos subconjuntos disjuntos Sx e Sy contendo x e y, respectivamente, e a adiciona à coleção para substituir Sx e Sy, que são excluídos dela.
      - EX: S = {1, 2, 3, 4, 5, 6}
        
        makeset(i) cria o conjunto {i} e aplicando esta operação seis vezes inicializa a estrutura para a coleção de seis conjuntos
        
        {1}, {2}, {3}, {4}, {5}, {6}.
        
        union(1, 4) e union(5, 2)
        
        {1, 4}, {5, 2}, {3}, {6},
        
        union(4, 5) e union(3, 6)
        
        1 more item...