Please enable JavaScript.

Coggle requires JavaScript to display documents.

Greedy technique - Coggle Diagram

- - - - O algoritmo de Prim constrói uma minimum spanning tree por meio de uma sequência de subárvores em expansão. A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto V de vértices do grafo. Em cada iteração, o algoritmo expande a árvore atual de maneira gulosa, simplesmente anexando a ela o vértice mais próximo que não está nessa árvore. (Por vértice mais próximo, queremos dizer um vértice que não está na árvore conectado a um vértice da árvore por uma aresta do menor peso. Ligações podem ser quebradas arbitrariamente.) O algoritmo para após todos os vértices do grafo terem sido incluídos na árvore sendo construído. Como o algoritmo expande uma árvore em 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 do grafoo. A árvore gerada pelo algoritmo é obtida como o conjunto de arestas usado para as expansões da árvore.
        
        O algoritmo de Prim torna necessário fornecer a cada vértice que não está na árvore atual as informações sobre a aresta mais curta conectando o vértice a um vértice da árvore. Podemos fornecer essas informações anexando dois rótulos a um vértice: o nome do vértice da árvore mais próximo e o comprimento (o peso) da aresta correspondente. Os vértices que não são adjacentes a nenhum dos vértices da árvore podem receber o rótulo ∞ indicando sua distância “infinita” aos vértices da árvore e um rótulo nulo para o nome do vértice da árvore mais próximo. (Alternativamente, podemos dividir os vértices que não estão na árvore em dois conjuntos, a “visitados” e o “não visitados”. Os visitados 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 não visitados são todos os outros vértices do grafo, chamados de "não visitados" porque ainda não foram afetados pelo algoritmo. Com esses rótulos, encontrar o próximo vértice para ser adicionado à árvore atual torna-se uma tarefa simples de encontrar um vértice com o menor rótulo de distância no conjunto V - VT. Os laços podem ser quebrados arbitrariamente.
        
        After we have identified a vertex u∗ to be added to the tree, we need to perform
        two operations:
        
        1 - Move u∗ from the set V − VT to the set of tree vertices VT .
        
        2 - For each remaining vertex u in V − VT that is connected to u∗ by a shorter edge than the u’s current distance label, update its labels by u∗ and the weight of the edge between u∗ and u, respectively.
        
        A eficiência do algoritmo de Prim depende das estruturas de dados escolhidas para o próprio grafo e para a fila de prioridades do conjunto V - VT cujas prioridades de vértice são as distâncias aos vértices da árvore mais próximos.
        
        A priority quee também pode ser implementada como uma heap mínima. Todas as propriedades principais das heaps permanecem válidas para as heaps mínimas, com algumas modificações óbvias. Por exemplo, a raiz de uma heap mínima contém o menor, em vez do maior elemento. A exclusão do menor elemento e a inserção de um novo elemento em uma heap mínima de tamanho n são operações de O (log n), assim coma a operação de alterar a prioridade de um elemento. Se um grafo é representado por suas listas de adjacência e a priority quee é implementada como uma heap mínima, o tempo de execução do algoritmo está em O (| E | log | V |). Isso ocorre porque o algoritmo executa | V | - 1 deleções do menor elemento e faz | E | verificações e, possivelmente, alterações na prioridade de um elemento em uma heap mínima de tamanho menor ou igual a | V |. Cada uma dessas operações é uma operação de O (log | V |).
- - - - O fato de que ET é na verdade uma árvore no algoritmo de Prim, mas geralmente apenas um subgrafo acíclico no algoritmo de Kruskal acaba sendo um obstáculo que pode ser superado. Aplicar os algoritmos de Prim e Kruskal ao mesmo pequeno grafo à mão pode criar a impressão de que o último é mais simples do que o primeiro. Esta impressão está errada porque, em cada uma de suas iterações, o algoritmo de Kruskal tem que verificar se a adição da próxima aresta às arestas já selecionadas criaria um ciclo. Não é difícil ver que um novo ciclo é criado se e somente se a nova aresta conecta dois vértices já conectados por um caminho, ou seja, se e somente se os dois vértices pertencem ao mesmo componente conectado. Observe também que cada componente conectado de um subgrafo gerado pelo algoritmo de Kruskal é uma árvore porque não tem ciclos
        
        Dadas essas observações, é conveniente usar uma interpretação ligeiramente diferente do algoritmo de Kruskal. 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 grafo. A floresta final consiste em uma única árvore, que é a minimum spanning tree do grafo. Em cada iteraçã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). Felizmente, existem algoritmos eficientes para fazer isso, incluindo a verificação crucial se dois vértices pertencem à mesma árvore. Eles são chamados de algoritmos de Union-Find.
        
        Disjoint Subsets and Union-Find Algorithms:
        
        O algoritmo de Kruskal é uma das várias aplicações que requerem uma partição dinâmica de algum conjunto de n elementos S em uma coleção de subconjuntos disjuntos S1, S2, ..., Sk. Depois de ser inicializada como uma coleção de n subconjuntos de um elemento, cada um contendo um elemento diferente de S, a coleção é submetida a uma sequência de operações mescladas de união e localização. (Observe que o número de operações de união em qualquer sequência deve ser limitada superiormente por n - 1 porque cada união aumenta o tamanho de um subconjunto em pelo menos 1 e há apenas n elementos em todo o conjunto S.)
        
        Thus, we are dealing here with an abstract data type of a collection of disjoint subsets of a finite set with the following operations:
        
        1 - makeset(x) creates a one-element set {x}. It is assumed that this operation can be applied to each of the elements of set S only once.
        
        2 - find(x) returns a subset containing x.
        
        3 - union(x, y) constructs the union of the disjoint subsets Sx and Sy containing x and y, respectively, and adds it to the collection to replace Sx and Sy, which are deleted from it.
        
        A maioria das implementações deste abstract data type usa um elemento de cada um dos subconjuntos disjuntos na coleção como o representante desse subconjunto. Algumas implementações não impõem quaisquer restrições específicas ao representante, outras exigem, digamos, que o menor elemento de cada subconjunto seja usado como o representante do subconjunto. Além disso, geralmente é assumido que os elementos do conjunto são (ou podem ser mapeados em) inteiros. Existem duas formas principais para implementar essa estrutura de dados. O primeiro, denominado quick find, otimiza a eficiência de tempo da operação find, o segundo, denominado quick union, otimiza a operação union.
        
        2 more items...