prim.c

最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n-1条边并使这个图仍然连通...为了得到最小生成树,人们设计了很多算法,最著名的有prim算法和kruskal算法。

#include <stdio.h>
#include <stdlib.h>
#define NUM 5
#define MAXINT 65535

void SearchMinPath (int passed[], int W[][NUM], int *cost)
{
	int i = 0, j = 0;
	int w_min = MAXINT;
	int father, son;
	/*选定具有最小权值的路线，并确定其父子结点*/
	for (i = 0; i < NUM; i++)
	{
		if (passed[i] == MAXINT) continue;
		for (j = 0; j < NUM; j++)
		{
			if (passed[j] == 1) continue;
            while (W[i][j] < MAXINT && W[i][j] < w_min && W[i][j] != 0)
			{
				w_min = W[i][j];
				father = i;
				son = j;
			}
		}
	}

	
	/*将选定的下一个结点加入遍历过的结点的集合,并将其在未遍历过的结点的集合中删去*/
	passed[son] = 1;
	*cost += W[father][son];
	printf("%5d,%5d,  cost  %d\n",father,son,*cost);
}

int main()
{
	int W[NUM][NUM] = {  {0,2,1,MAXINT,MAXINT},
		                 {2,0,2,MAXINT,3},
		                 {1,2,0,4,2},
		                 {MAXINT,MAXINT,4,0,1},
		                 {MAXINT,3,2,1,0} };
  int i;
  int passed[NUM];
  int cost = 0;
  for (i = 0; i < NUM; i++)
  {
	  passed[i] = MAXINT;
  }
  passed[0] = 1;    //定制从第一个点为起点
  for ( i = 0; i < NUM - 1; i++)
  {
  	SearchMinPath (passed, W, &cost);
  }
  return 1;
}