Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST - Coggle Diagram
MST
O algoritmo de Prim constrói uma árvore geradora mínima através de uma sequência
de expansão de subárvores.
A subárvore inicial em tal sequência consiste em um único vértice selecionado arbitrariamente do conjunto V dos vértices do grafo.
Em cada iteração, o algoritmo expande a árvore atual de maneira gananciosa simplesmente anexando ao vértice mais próximo que não está nessa árvore. (Pelo vértice mais próximo, queremos dizer um vértice que não está na árvore conectado a um vértice na árvore por uma aresta de menor peso. 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.
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 grafo.
A árvore gerada pelo algoritmo é obtida como o conjunto de arestas usadas para as expansões da árvore.
O algoritmo de Prim sempre produz uma árvore geradora mínima.
A eficiência do algoritmo de Prim depende das estruturas de dados escolhidas para o próprio grafo e para a fila de prioridade do conjunto V − VT cuja prioridade dos vértices são as distâncias até os vértices da árvore mais próximos.
Em particular, se um grafo é 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 será em theta(|V|^2).
De fato, em cada uma das |V | − 1 iterações, a matriz que implementa a fila de prioridade é percorrida 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 uma heap mínima.
A exclusão do menor elemento e a inserção de um novo elemento em um heap mínimo de tamanho n são operações O(log n).
Se um grafo é representado por suas listas de adjacências e a fila de prioridade é implementada como um heap mínimo, o tempo de execução do algoritmo é O(|E| log |V |).
Isso ocorre porque o algoritmo executa |V | − 1 exclusões do menor elemento e faz |E| verificações e, possivelmente, mudanças de prioridade de um elemento em uma pilha mínima de dimensão não superior a |V |.
A natureza do algoritmo de Prim torna necessário fornecer cada vértice não presente na árvore atual com as informações sobre a aresta mais curta conectando o vértice para um vértice de árvore.
Podemos fornecer essas informações anexando duas etiquetas 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 “franja” e o “invisível”. 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 não vistos são todos os outros vértices do grafo, chamados “invisíveis” porque ainda não foram afetados pelo algoritmo.). Com esses rótulos,
encontrar o próximo vértice a ser adicionado à árvore atual torna-se uma tarefa simples de encontrar um vértice com o menor rótulo de distância no conjunto.
Após identificarmos um vértice u∗ a ser adicionado à árvore, precisamos realizar duas operações:
Mover u∗ do conjunto V − VT para o conjunto de vértices da árvore VT .
Para cada vértice u restante em V − VT que está conectado a u∗ por uma aresta menor do que o rótulo de distância atual de u, atualize seus rótulos por u∗ e o peso
da aresta entre u∗ e u, respectivamente.
O algoritmo de Kruskal analisa uma árvore geradora 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.
Consequentemente, o algoritmo constrói uma árvore geradora mínima como uma sequência em expansão de subgrafos que são sempre acíclicos, mas não estão necessariamente conectados nos estágios intermediários do algoritmo.
O algoritmo começa ordenando as arestas do grafo em ordem não decrescente de seus pesos. Então, começando com o subgrafo vazio, ele varre esta lista ordenada, adicionando a próxima aresta da lista ao subgrafo atual se tal inclusão não criar um ciclo e simplesmente pular a aresta.
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 geradora mínima 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 as mesmas, une-as em uma árvore maior adicionando a aresta (u, v).
Algoritmos de busca de união serve para verificar se dois vértices pertencem à mesma árvore.
Dependendo do algoritmo de ordenação utilizado, a eficiência de tempo do algoritmo de Kruskal estará em
O(|E| log |E|).
Uma árvore geradora de um grafo conectado não direcionado é seu subgrafo acíclico (ou seja, uma árvore) que contém todos os vértices do grafo. Se tal grafo tem pesos atribuídos às suas arestas, uma árvore geradora mínima é sua extensão árvore 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.