Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim, Algoritmode Kruskal - Coggle Diagram
Algoritmo de Prim
funcionamento
-
-
cada iteração, anexa o vertice MAIS PROXIMO que ainda não está na árvore
passo a passo
-
2 - repete n-1 vezes: encontra uma aresta de menor peso (v, u) que conecta um vertice v (detro de T) a um vertice u (fora de T)
3 - adiciona u a T e a aresta (v, u*) ao conjunto de arestas da MST
arvore geradora minima
conecta n pontos da forma mais barata possivel, garantindo um caminho entre todos os pares
grafo conectado, sem ciclos que contem todos os vertices iniciais
-
-
Algoritmode Kruskal
-
-
arvore geradora minima
encontrar um subgrafo sem ciclos com (|v| - 1) arestas que conecta todos os vertices com a menor soma de pesos
-
-