Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmo de Prim - Coggle Diagram
Algoritmo de Prim
Como funciona?
Tendo um grafo não dirigido, conexo e com custo nas arestas, o algoritmo de prim cultiva uma subarvore de G até que ela se torne geradora, dessa forma, agora teremos uma árvore MST.
Pseudocódigo:
-
Definição da franja: A franja contém apenas os vértices que não estão na árvore, mas são adjacentes a
pelo menos um vértice da árvore.
Tipos de implementação
Simples
Leva um tempo O(n*m), o que já não passa a ser um tempo ideal, pois as arvores tendem a ser grandes.
-
-
