A minimum spanning tree (MST) on a weighted graph is a spanning tree in which the sum of the weights of the edges is at a minimum. Finding MSTs is important in areas like the design of electrical networks.
Prim’s algorithm is a greedy algorithm for finding an MST on a weighted graph \(G\) . It goes as follows:
 Create an empty set \(T,\) for the tree
 Choose a starting vertex
 While \(T\) contains fewer than \(Order(G) – 1\) edges:

 Find the cheapest edge with one endpoint in \(T\) and one endpoint outside it
 Add it to \(T\)
Below is an implementation in C. By sorting the edges by weight first, I have made it more efficient to find the next cheapest edge than using an unordered array. It could be made more efficient still by the use of a data structure like a heap.
#include <stdlib.h> typedef struct { unsigned int first; unsigned int second; unsigned int weight; } weighted_edge; /* Compare two weighted edges by weight */ int weighted_edge_compare(const weighted_edge *edge1, const weighted_edge *edge2) { return edge1>weight  edge2>weight; } unsigned int prim(weighted_edge *edges, unsigned int size, unsigned int order, weighted_edge **mst) { *mst = malloc((order  1) * sizeof(weighted_edge)); unsigned int *vertices = calloc(order, sizeof(unsigned int)); unsigned int i; unsigned int cost = 0; if (*mst == NULL  vertices == NULL) { free(*mst); free(vertices); return 0; } /* Sort the edges by weight */ qsort(edges, size, sizeof(weighted_edge), (int(*)(const void *, const void *))weighted_edge_compare); /* Choose a starting vertex */ vertices[0] = 1; /* Main loop */ for (i = 0; i < order  1; i++) { /* Find the cheapest edge with one endpoint in the tree and one not */ unsigned int e; int cheapest = 1; for (e = 0; e < size && cheapest == 1; e++) { if ((vertices[edges[e].first] == 1 && vertices[edges[e].second] == 0)  (vertices[edges[e].first] == 0 && vertices[edges[e].second] == 1)) { cheapest = e; } } if (cheapest == 1) { /* Graph wasn't connected properly */ free(*mst); *mst = NULL; free(vertices); return 0; } /* Add the edge */ (*mst)[i] = edges[cheapest]; /* Add the vertices (one will already be there) */ vertices[edges[cheapest].first] = 1; vertices[edges[cheapest].second] = 1; /* Add the cost */ cost += edges[cheapest].weight; } free(vertices); return cost; }
Here is an example program that finds an MST on the graph shown at the top:
#include <stdlib.h> #include <stdio.h> /* Calculate the nth triangular number T(n) */ unsigned int triangular_number(unsigned int n) { return (n * (n + 1)) / 2; } /* Construct a complete weighted graph on v vertices */ unsigned int complete_weighted_graph(unsigned int v, weighted_edge **edges) { const unsigned int n = triangular_number(v  1); unsigned int i, j, k; *edges = malloc(n * sizeof(weighted_edge)); if (edges != NULL) { for (i = 0, k = 0; i < v  1; i++) { for (j = i + 1; j < v; j++) { (*edges)[k].first = i; (*edges)[k].second = j; (*edges)[k].weight = k + 1; k++; } } } return n; } void print_edges(const weighted_edge *edges, unsigned int n) { unsigned int e; for (e = 0; e < n; e++) { printf("(%u, %u, %u) ", edges[e].first, edges[e].second, edges[e].weight); } putchar('\n'); } int main(void) { weighted_edge *edges; const unsigned int order = 5; const unsigned int size = complete_weighted_graph(order, &edges); weighted_edge *mst; unsigned int cost = prim(edges, size, order, &mst); printf("Cost is %u\n", cost); print_edges(mst, order  1); free(mst); free(edges); return 0; }
The output:
Cost is 10 (0, 1, 1) (0, 2, 2) (0, 3, 3) (0, 4, 4)