Algoritmo de Prim
Origem: Wikipédia, a enciclopédia livre.
O algoritmo de Prim é um algoritmo em teoria dos grafos que busca uma árvore geradora mínima para um grafo conexo com pesos. O algoritmo de Prim é um exemplo de um algoritmo guloso.
- O subconjunto S forma uma única árvore, e a aresta segura adicionada a S é sempre uma aresta de peso mínimo conectando a árvore a um vértice que não esteja na árvore.
- A árvore começa por um vértice qualquer e cresce até que "gere" todos os vértices em V.
- A cada passo, uma aresta leve é adicionada à árvore S, conectando S a um vértice de GS = (V;S).
- De acordo com o teorema anterior, quando o algoritmo termina, as arestas em S formam uma árvore geradora mínima.
A ordem de complexidade para o algoritmo de Prim é 
.
