Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmo de Kruskal, Aplicar o algoritmo de Prim e de…
Algoritmo de Prim
Árvore Geradora
A árvore geradora de um grafo adirecionado conectado é seu subgrafo conectado acíclico que contenha todos os vértices do grafo. Se o grafo tem pesos associados para suas arestas, a árvore geradora se torna uma MST, árvore geradora mínima.
-
A natureza do algoritmo de prim faz necessário dizer a todo vértice que não está na MST quem é a menor aresta conectando um vértice a um vértice da MST.
O candidatos para o próximo vértice da MST são todos os vértices adjacentes a pelo menos um vértice da MST, mas que não pertencem a ela.
-
Algoritmo de Kruskal
Já que a natureza do algoritmo de Kruskal se baseia no fato de que não podem haver ciclos, podemos usar uma DSU para implementá-lo, já que para não ter ciclos, teremos que construir uma árvore com base em conjuntos disjuntos de vértices.
-
-
O algoritmo de Kruskal olha a MST de um grafo conectado com pesos como um subgrafo acíclico de V-1 arestas cuja soma das arestas é a menor possível.
Dese modo, o algoritmo constrói uma sequência de subgrafos acíclicos mas que não necessariamente estão conectados nas fases intermediárias do algoritmo.
O algoritmo sorta as arestas em ordem não decrescente, então vai incluir a próxima aresta na lista do subgrafo atual se tal inclusão não faz um ciclo.
-
Aplicar o algoritmo de Prim e de Kruskal no mesmo grafo pequeno pode dar a impressão que Kruskal é mais simples do que Prim, mas isso não é verdade pois Kruskal tem que ficar checando se formam-se ciclos ou não.