Please enable JavaScript.
Coggle requires JavaScript to display documents.
MST (Minimum Spanning Tree) - Coggle Diagram
MST (Minimum Spanning Tree)
O problema consiste em:
Dado n pontos, conecte eles da forma mais econômica possível de forma que sempre vai haver um caminho entre cada par de pontos e que esse caminho tenha o menor peso total possível
Para a resolução desse problema vamos trabalhar com grafos, onde os postos vão ser os vértices e as conexões vão ser as arestas
O que é uma Spaning Tree?
Uma Spanning Tree de um grafo (sem direção) é um subgrafo acíclico (uma árvore) que contem todos os vértices do grafo. Em um grafo de pesos temos a
Minimum Spanning Tree
(MST) que é a Spanning Tree com menor peso, onde o peso de uma Spanning Tree é a soma dos pesos de suas arestas
Porém para resolver o problema da MST não podemos verificar cada Spanning Tree, pois o número de Spanning Trees cresce de maneira exponencial e gerar Spanning Trees não é tão simples, por isso é melhor utilizar outro(s) algoritmo(s) para encontrar a MST
Algoritmo de Prim
Esse algoritmo constrói a MST através de uma sequencia de sub-árvores em expansão.
A sub-árvore inicial é composta por um único vértice, que pode ser escolhido arbitrariamente
Em cada iteração, o algoritmo expande a árvore atual adicionando o vértice mais próximo que não está na árvore (que é um vértice que está conectado a um vértice contido na árvore e que a aresta que os conecta tem o menor peso)
O algoritmo para depois de vértices serem incluídos
A arvore gerada é obtida como um conjunto de arestas usadas na expansão da árvore
Esse processo vai ocorrer n-1 vezes, onde n é o número de vértices no grafo
Para utilizar esse algoritmo é necessário ter, para cada nó fora da árvore, a informação sobre a menor aresta conectando um vértice para um vértice da árvore
Para isso podemos adicionar dois parâmetros a cada vértice, O nome do vértice mais próximo e o peso da aresta que os conecta
Os vértices que não tenham adjacências com vértices da árvore ficam com o nome do vértice mais próximo como null e com a distância entre eles igual a infinito
Com esse rótulos fica muito mais fácil encontrar o vértice mais próximo para adicionar a árvore, é só ver quem, dos vértices que estão fora da árvore, tem a menor distância para um vértice da árvore
Depois de identificar um vértice u* para ser adicionado temos que fazer duas operações:
Mover u* do conjunto dos vértice que não estão na árvore para o que estão
Para cada vértice restante no conjunto dos vértices que não estão na árvore que esta conectado a u
por uma aresta mais curta que o rótulo de distância atual, atualize seus rótulos com u
no nome do mais próximo e com a distância para u* no rótulo da distância
A eficiência desse algoritmo vai depender de quais estruturas de dados foram usadas:
Se o garfo for representado como matriz e a fila de prioridade for feita como um array desordenado, a eficiência fica na ordem de (|V|^2)
Se o grafo for representado como lista de adjacência e a fila de prioridade como uma heap mínima, a eficiência fica na ordem de (|E|*log|V|)
Tem o código muito parecido com o Dijkstra
Algoritmo De Kruskal
Esse algoritmo também vai construindo a MST através de expansões de subgrafo, porém não é garantido que nas expansões intermediárias o grafo resultante (árvore) vai estar conectada
Antes de tudo cria-se uma lista ordenada de maneira não decrescente com todas as arestas (a ordem vai ser feita de acordo com os pesos das arestas)
Iniciando com um grafo vazio, o algoritmo adiciona a próxima aresta ao subgrafo, se essa aresta não formar um ciclo ao ser incluída, caso contrário essa aresta é ignorada, e o processo se repete para a próxima
Um novo ciclo só é 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
Heap minima
Note que inicialmente temos uma floresta com várias árvores unitárias que contém apenas um vértice (n árvores, uma para cada vértice), ao fim do processo temos os mesmos vértices na floresta, porém arestas foram adicionadas deixando a floresta com apenas uma árvore, a MST
???Subconjuntos disjuntos e algoritmos de localização de união???
è um tipo abstrato de dados que tem duas operações, que é como uma floresta de árvores unitárias, cada árvore unitaria vai se ligando a outra até termos uma MST (isso segundo Krusal)
Find
Acha o representante de um conjunto
Encontra a "raiz de uma árvore)
Union
Une dois conjuntos
(liga duas arvores da floresta)
Quando a gente cria esse tipo de dado a gente diz quantas arvores unitárias vão haver nele
Existe duas maneiras de implementar, uma que o find é mais rápido e outra que o Union é mais rápido
Se for usado um bom algoritmo de algoritmos de localização de união a eficiência depende principalmente do maneira que a ordenação das arestas vai ser feita, se isso for feito de maneira eficiente, então a eficiência do algoritmo deve ficar na ordem de (|E|*log|E|)
É melhor que Prim se o grafo for esparso