Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm, Kruskal’s Algorithm, Disjoint Subsets and Union-Find…
Prim's Algorithm
Funcionalidade
O algoritmo de Prim constrói uma árvore de abrangência mínima através 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 a partir do conjunto V dos vértices do grafo.
Em cada iteração, o algoritmo expande a árvore atual da maneira gananciosa simplesmente anexando a ela o vértice mais próximo que não está nessa árvore. (Pelo vértice mais próximo, queremos dizer um vértice não na árvore ligado a um vértice na árvore por uma aresta do menor peso. Os laços podem ser quebrados arbitrariamente.)
O algoritmo para depois que todos os vértices do grafo foram incluídos na árvore que está sendo construída. Uma vez que 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 grafo. A árvore gerada pelo algoritmo é obtida como o conjunto de arestas usadas para as expansões de árvore
A natureza do algoritmo de Prim torna necessário fornecer a cada vértice não na árvore atual a informação sobre a borda mais curta que conecta o vértice a um vértice de á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 borda 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" para os vértices da árvore e um rótulo nulo para o nome do vértice da árvore mais próximo.
Com esses rótulos, encontrar o próximo vértice a ser adicionado à árvore atual T = {Vt , Et} 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
Depois de termos identificado um vértice u a ser adicionado à árvore, precisamos de efectuar duas operações:
Mova u do conjunto V - VT para o conjunto de vértices de árvore VT
Para cada vértice remanescente u em V - VT que está conectado a u por uma borda mais curta do que o rótulo de distância atual de u, atualize seus rótulos por u e o peso da borda entre u e u, respectivamente.
Uma árvore de abrangência de um grafo conectado não direcionado é seu subgrafo acíclico conectado (isto é, uma árvore) que contém todos os vértices do grafo. Se tal grafo tem pesos atribuídos às suas bordas, uma árvore de abrangência mínima é a sua árvore de abrangência do menor peso, onde o peso de uma árvore é definido como a soma dos pesos em todas as suas bordas. O problema da árvore de abrangência mínima é o problema de encontrar uma árvore de abrangência mínima para um dado grafo conectado ponderado.
Em particular, se um gráfico é representado por sua matriz de peso e a fila de prioridade é implementada como uma matriz não ordenada, o tempo de execução do algoritmo estará em Θ(|V|²). De fato, em cada uma das iterações |V | - 1, o array que implementa a fila de prioridade é percorrido para encontrar e excluir o mínimo e, em seguida, atualizar, se necessário, as prioridades dos vértices restantes.
Também podemos implementar a fila de prioridade como um min-heap. Um min-heap é uma imagem espelhada da estrutura do heap.cNa verdade, ela pode ser implementada construindo um heap depois de negar todos os valores-chave dados. Ou seja, um min-heap é uma árvore binária completa em que cada elemento é menor ou igual aos seus filhos. Todas as propriedades principais dos heaps permanecem válidas para min-heaps, com algumas modificações óbvias. Por exemplo, a raiz de um min-heap contém o menor elemento em vez do maior. A exclusão do menor elemento e a inserção de um novo elemento em um min-heap de tamanho n são operações O(log n), assim como a operação de alterar a prioridade de um elemento
Se um gráfico é representado por suas listas de adjacência e a fila de prioridade é implementada como um min-heap, o tempo de execução do algoritmo está em O(|E| log |V|). Isso ocorre porque o algoritmo executa |V| - 1 exclusões do menor elemento e faz |E| verificações e, possivelmente, alterações da prioridade de um elemento em um min-heap de tamanho não superior a |V|. Cada uma dessas operações, como observado anteriormente, é uma operação O(log |V|). Assim, o tempo de execução desta implementação do algoritmo de Prim é em (visto que em um grafo
conectado, |V| − 1 ≤ |E|):
(|V| − 1 + |E|)O(log |V|) = O(|E| log |V|)
Kruskal’s Algorithm
Funcionalidade
O algoritmo começa classificando as arestas do gráfico em ordem não decrescente de seus pesos. Então, começando com o subgrafo vazio, ele verifica essa lista ordenada, adicionando a próxima borda da lista ao subgrafo atual se tal inclusão não criar um ciclo e simplesmente pulando a borda caso contrário.
A correção do algoritmo de Kruskal pode ser provada repetindo os passos essenciais da prova do algoritmo de Prim dada na seção anterior. O fato de que ET é realmente uma árvore no algoritmo de Prim, mas geralmente apenas um subgrafo acíclico no algoritmo de Kruskal acaba por ser um obstáculo que pode ser superado.
Em cada uma de suas iterações, o algoritmo de Kruskal tem que verificar se a adição da próxima borda às bordas 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. Note também que cada componente conectado de um subgrafo gerado pelo algoritmo de Kruskal é uma árvore porque não tem ciclos
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 dado 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 é 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 das arestas do grafo, encontra as árvores que contêm os vértices u e v e, se essas árvores não forem as mesmas, as une em uma árvore maior adicionando a aresta (u, v).
O algoritmo de Kruskal analisa uma árvore de abrangência mínima de um grafo conectado ponderado G = {V,E} como um subgrafo acíclico com |V | - 1 arestas para as quais a soma dos pesos das arestas é a menor. (Não é difícil provar que tal subgrafo deve ser uma árvore.) Consequentemente, o algoritmo constrói uma árvore de abrangência mínima como uma sequência em expansão de subgrafos que são sempre acíclicos, mas não são necessariamente conectados nos estágios intermediários do algoritmo.
Com um algoritmo de ordenação eficiente, a eficiência temporal do algoritmo de Kruskal será em O(|E| log |E|).
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 inicializado 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 de união e busca misturadas. (Observe que o número de operações de união em qualquer sequência deve ser limitado acima por n - 1 porque cada união aumenta o tamanho de um subconjunto pelo menos em 1 e há apenas n elementos em todo o conjunto S.)
Assim, estamos aqui a lidar com um tipo de dados abstracto de uma colecção de subconjuntos disjuntos de um conjunto finito com as seguintes operações:
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.
Existem duas alternativas principais para implementar essa estrutura de dados. O primeiro, chamado de quick find, otimiza a eficiência de tempo da operação de busca; o segundo, chamado de quick union, otimiza a operação de união.
Quick find (busca rápida)
A busca rápida usa uma 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 último elementos da lista, juntamente com o número de elementos na lista
Sob este esquema, a implementação de makeset(x) requer atribuir o elemento correspondente no array representativo a x e inicializar a lista vinculada correspondente a um único nó com o valor x. A eficiência de tempo desta operação é obviamente em Θ(1), e, portanto, a inicialização de n subconjuntos singleton é em Θ(n).
A eficiência de find(x) também está em Θ(1): tudo o que precisamos fazer é recuperar o representante de x na matriz representativa
Executar union(x, y) leva mais tempo. Uma solução simples simplesmente anexaria a lista de y ao final da lista de x, atualizaria as informações sobre seu representante para todos os elementos na lista de y e, em seguida, excluiria a lista de y da coleção
É fácil verificar, no entanto, que com este algoritmo a sequência de operações de união união(2, 1), união(3, 2), . . . , união(i + 1, i), . . , união(n, n - 1) é executado no tempo Θ(n²)
Uma maneira simples de melhorar a eficiência geral de uma sequência de operações de união é sempre anexar a mais curta das duas listas à mais longa, com laços quebrados arbitrariamente. Claro, o tamanho de cada lista é assumido para estar disponível por, digamos, armazenar o número de elementos no cabeçalho da lista. Essa modificação é chamada de união por tamanho. Embora não melhore a eficiência do pior caso de uma única aplicação da operação da união (ainda está em Θ(n)), o pior caso de tempo de execução de qualquer sequência legítima de operações de união por tamanho acaba sendo em O(n log n). Assim, para união por tamanho, a eficiência temporal de uma sequência de no máximo n - 1 uniões e m finds encontra-se em O(n log n + m).
Otimiza a eficiência temporal
Quick union (união rápida)
A união rápida, a segunda principal alternativa para implementar subconjuntos disjuntos, representa cada subconjunto por uma árvore enraizada. 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 de filhos para seus pais. Além disso, um mapeamento dos elementos do conjunto para seus nós de árvore implementados, digamos, como uma matriz de ponteiros, é mantido.
Para esta implementação, makeset(x) requer a criação de uma árvore de nó único, que é uma operação Θ(1); portanto, a inicialização de n subconjuntos singleton está em Θ(n).
Uma união(x, y) é implementada anexando a raiz da árvore de y à raiz da árvore de x (e excluindo a árvore de y da coleção fazendo o ponteiro para sua raiz nulo). A eficiência de tempo desta operação é claramente Θ(1).
Um find(x) é executado seguindo a cadeia de ponteiros do nó contendo x para a raiz da árvore cujo elemento é retornado como representante do subconjunto. Assim, a eficiência de tempo de uma única operação de busca está em O(n) porque uma árvore representando um subconjunto pode degenerar em uma lista vinculada com n nós.
Otimiza a operação de união. Assim, para união rápida, a eficiência de tempo de uma sequência de no máximo n - 1 uniões e m encontra-se em O(n + m log n). Na verdade, uma eficiência ainda melhor pode ser obtida combinando qualquer variedade de união rápida com compressão de caminho (path compression)
Este limite de tempo pode ser melhorado. A maneira direta de fazer isso é sempre executar uma operação de união anexando uma árvore menor à raiz de uma maior, com laços quebrados arbitrariamente. O tamanho de uma árvore pode ser medido pelo número de nós (esta versão é chamada união por tamanho) ou pela sua altura (esta versão é chamada união por classificação ou union by rank). É claro que essas opções exigem o armazenamento, para cada nó da árvore, do número de descendentes de nós ou da altura da subárvore enraizada nesse nó, respectivamente. Pode-se facilmente provar que, em qualquer caso, a altura da árvore será logarítmica, tornando possível executar cada achado no tempo O(log n).