Tag Archives: Prim

Prim’s Minimum Spanning Tree (MST) Algorithm in C

Weighted graph showing a Minimum Spanning Tree (MST)

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:

  1. Create an empty set \(T,\) for the tree
  2. Choose a starting vertex
  3. While \(T\) contains fewer than \(Order(G) – 1\) edges:
    1. Find the cheapest edge with one endpoint in \(T\) and one endpoint outside it
    2. 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)