1  
   2  #include <stdio.h>
   3  
   4  /*
   5  	The input file (weight.txt) look something like this
   6  		4
   7  		0 0 0 21
   8  		0 0 8 17
   9  		0 8 0 16
  10  		21 17 16 0
  11  
  12  	The first line contains n, the number of nodes.
  13  	Next is an nxn matrix containg the distances between the nodes
  14  	NOTE: The distance between a node and itself should be 0
  15  */
  16  
  17  int n; /* The number of nodes in the graph */
  18  
  19  int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
  20  			if there is no path between i and j, weight[i][j] should
  21  			be 0 */
  22  
  23  char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
  24  			spanning tree; 0 otherwise*/
  25  
  26  int d[100]; /* d[i] is the distance between node i and the minimum spanning
  27  		tree; this is initially infinity (100000); if i is already in
  28  		the tree, then d[i] is undefined;
  29  		this is just a temporary variable. It's not necessary but speeds
  30  		up execution considerably (by a factor of n) */
  31  
  32  int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
  33  			linked to in order to get a distance of d[i] */
  34  
  35  /* updateDistances(int target)
  36  	should be called immediately after target is added to the tree;
  37  	updates d so that the values are correct (goes through target's
  38  	neighbours making sure that the distances between them and the tree
  39  	are indeed minimum)
  40  */
  41  void updateDistances(int target) {
  42  	int i;
  43  	for (i = 0; i < n; ++i)
  44  		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
  45  			d[i] = weight[target][i];
  46  			whoTo[i] = target;
  47  		}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	FILE *f = fopen("dist.txt", "r");
  52  	fscanf(f, "%d", &n);
  53  	int i, j;
  54  	for (i = 0; i < n; ++i)
  55  		for (j = 0; j < n; ++j)
  56  			fscanf(f, "%d", &weight[i][j]);
  57  	fclose(f);
  58  
  59  	/* Initialise d with infinity */
  60  	for (i = 0; i < n; ++i)
  61  		d[i] = 100000;
  62  
  63  	/* Mark all nodes as NOT beeing in the minimum spanning tree */
  64  	for (i = 0; i < n; ++i)
  65  		inTree[i] = 0;
  66  
  67  	/* Add the first node to the tree */
  68  	printf("Adding node %c\n", 0 + 'A');
  69  	inTree[0] = 1;
  70  	updateDistances(0);
  71  
  72  	int total = 0;
  73  	int treeSize;
  74  	for (treeSize = 1; treeSize < n; ++treeSize) {
  75  		/* Find the node with the smallest distance to the tree */
  76  		int min = -1;
  77  		for (i = 0; i < n; ++i)
  78  			if (!inTree[i])
  79  				if ((min == -1) || (d[min] > d[i]))
  80  					min = i;
  81  
  82  		/* And add it */
  83  		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
  84  		inTree[min] = 1;
  85  		total += d[min];
  86  
  87  		updateDistances(min);
  88  	}
  89  
  90  	printf("Total distance: %d\n", total);
  91  
  92  	return 0;
  93  }
  94