Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Prim e Kruskal - Coggle Diagram
Algoritmos de Prim e Kruskal
Prim
Dado N pontos, devemos conectá-los da maneira menos custosa possível de forma que haja um caminho entre todos eles (menor soma entre os pesos das arestas de uma subárvore de um grafo)
Achar a subárvore com o menor valor
Cada iteração, o algoritmo expande em 1 a subárvore atual com a inclusão de um vértice que ainda não estava na subárvore
Os vértices não acessados no algoritmo devem possuir um símbolo especial para serem identificados, junto com a informação do caminho mais curto para a árvore
Depois de achar o vértice correto:
Mover o vértice para a árvore
Para cada vértice ainda fora da árvore, atualizar o vértice de menor distância
Eficiência
Matriz de adjacência- Theta V^2
Lista de adjacência + min heap- O(E log V), pois, em um grafo conectado, V - 1 <= E
Kruskal
Outra alternativa para o problema (que pode ser chamado de Minimum spanning tree)
Na sequência de subgrafos formados, eles não são necessariamente conectados, mas sempre acíclicos
Ordenar as arestas, adiciona-las ao subgrafo vazio desde que não formem um ciclo (ou seja, tenham uma aresta entre vértices já conectados)
Cada passo pode formar uma floresta, sendo cada árvore unificado no final do algoritmo
Eficiência em O(E log E) fazendo uso de um algoritmo union find
Uion-Find
Unir vértices inicilamente isolados
Makeset- set inicial
Find- achar união
Union- fazer união
Pode ser representado por uma listas de adjacência (uma para cada subárvore)
Forma otimizada - unir as subárvores menores na maior (eficiência- n log n + m) -> quickfind
Outra forma - cada árvore tem seu representativo conectado em uma subarvore iniciada com um único node (O( n + m log n)) -> quickunion