DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

The is a straight-forward implementation of Prim's Algorithm for finding the minimum spanning tree of a graph. A detailed explanation is given <a href="http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm/">here</a>.

#include <stdio.h> /* The input file (weight.txt) look something like this 4 0 0 0 21 0 0 8 17 0 8 0 16 21 17 16 0 The first line contains n, the number of nodes. Next is an nxn matrix containg the distances between the nodes NOTE: The distance between a node and itself should be 0 */ int n; /* The number of nodes in the graph */ int weight[100][100]; /* weight[i][j] is the distance between node i and node j; if there is no path between i and j, weight[i][j] should be 0 */ char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum spanning tree; 0 otherwise*/ int d[100]; /* d[i] is the distance between node i and the minimum spanning tree; this is initially infinity (100000); if i is already in the tree, then d[i] is undefined; this is just a temporary variable. It's not necessary but speeds up execution considerably (by a factor of n) */ int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be linked to in order to get a distance of d[i] */ /* updateDistances(int target) should be called immediately after target is added to the tree; updates d so that the values are correct (goes through target's neighbours making sure that the distances between them and the tree are indeed minimum) */ void updateDistances(int target) { int i; for (i = 0; i < n; ++i) if ((weight[target][i] != 0) && (d[i] > weight[target][i])) { d[i] = weight[target][i]; whoTo[i] = target; } } int main(int argc, char *argv[]) { FILE *f = fopen("dist.txt", "r"); fscanf(f, "%d", &n); int i, j; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) fscanf(f, "%d", &weight[i][j]); fclose(f); /* Initialise d with infinity */ for (i = 0; i < n; ++i) d[i] = 100000; /* Mark all nodes as NOT beeing in the minimum spanning tree */ for (i = 0; i < n; ++i) inTree[i] = 0; /* Add the first node to the tree */ printf("Adding node %c\n", 0 + 'A'); inTree[0] = 1; updateDistances(0); int total = 0; int treeSize; for (treeSize = 1; treeSize < n; ++treeSize) { /* Find the node with the smallest distance to the tree */ int min = -1; for (i = 0; i < n; ++i) if (!inTree[i]) if ((min == -1) || (d[min] > d[i])) min = i; /* And add it */ printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A'); inTree[min] = 1; total += d[min]; updateDistances(min); } printf("Total distance: %d\n", total); return 0; }