Algoritmo de PRim

void brutePrim( Graph G, Vertex parent[]) { Vertex v, w, v0, w0; link p; for (w = 0; w < G->V; w++) parent[w] = -1; parent[0] = 0; while (1) { double minprice = INFINITO; for (v = 0; v < G->V; v++) if (parent[v] != -1) for (p = G->adj[v]; p != NULL; p = p->next) if (parent[p->w] == -1 && minprice > p->cost) { minprice = p->cost; v0 = v; w0 = p->w; } if (minprice == INFINITO) break; /* A */ parent[w0] = v0; }
}

/* Recebe grafo G com custos arbitrários nas arestas e calcula uma MST da componente de G que contém o vértice 0. A função armazena a MST no vetor parent, tratando-a como uma arborescência com raiz 0. */

/* O grafo G e os custos são representados por uma listas de adjacência. A função supõe que a constante INFINITO é maior que o custo de qualquer aresta. Supõe também que o grafo tem no máximo maxV vértices. O código é uma versão melhorada do Programa 20.3, p.238, de Sedgewick. */ void GRAPHmstP1( Graph G, Vertex parent[]) { Vertex v0, w, frj[maxV]; link p; double price[maxV], c; for (w = 0; w < G->V; w++) { parent[w] = -1; price[w] = INFINITO; } parent[0] = 0; for (p = G->adj[0]; p != NULL; p = p->next) { w = p->w; c = p->cost; price[w] = c; frj[w] = 0; } while (1) { double minprice = INFINITO; for (w = 0; w < G->V; w++) if (parent[w] == -1 && minprice > price[w]) minprice = price[v0=w]; if (minprice == INFINITO) break; parent[v0] = frj[v0]; for (p = G->adj[v0]; p != NULL; p = p->next) { w = p->w; c = p->cost; if (parent[w] == -1 && price[w] > c) { price[w] = c; frj[w] = v0; } } }