Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal, Union-Find e Subsets - Coggle…
Algoritmo de Prim
Modo de funcionamento
Busca-se formar uma subárvore com os vértices do grafo original em que a soma total dos pesos das arestas é a menor possível
O algoritmo de Prim constrói uma árvore dessas através de uma sequência crescente de subárvores, em que, a cada iteração, o algoritmo expande a árvore atual anexando a ela o vértice mais próximo a essa árvore (levando em consideração o peso das arestas)
-
-
-
Algoritmo de Kruskal
O algoritmo consiste em ordenar as arestas do grafo em ordem não-decrescente de acordo com seus pesos. O algoritmo percorre essa lista, adicionando novas arestas à árvore, se essa adição não der origem a um ciclo
Para fazer a verificação necessária para que o algoritmo de Kruskal possa rodar de forma correta e, sobretudo, eficiente, podemos fazer uso dos algoritmos de Union-Find
Também é considerado um método "greedy" para encontrar caminhos em um grafo, mas de uma forma diferente da que o algoritmo de Prim faz
Union-Find e Subsets
Para implementar essa estrutura de dados, temos duas alternativas
-
-
Definimos um novo tipo abstrato de dados para auxiliar na resolução de problemas que requerem que operações de union e de find
Esse tipo faz uso das propriedades de um conjunto disjunto de elementos finitos, e que respeitam algumas operações
-
-
union(x,y)
Realiza a união dos subconjuntos às quais x e y fazem parte, respectivamente