prim.cpp

一个生成最小树的算法

// prim.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "string.h"
#include "malloc.h"
#define MAXVEX 6
#define MAX 32767
int c[MAXVEX][MAXVEX]={MAX,MAX,MAX,5,35,70,
			               MAX,MAX,29,MAX,MAX,MAX,
			               MAX,29,MAX,30,25,MAX,
			               5,MAX,30,MAX,10,20,
			               35,MAX,25,10,MAX,MAX,
			               70,MAX,MAX,20,MAX,MAX};
void prim(int n);
int main(int argc, char* argv[])
{
	prim(MAXVEX);
	return 0;
}

void prim(int n)
{
int *lowcost;
int *closest;
int i,j,k,min,mid;
lowcost=(int *)malloc(sizeof(int)*n);
closest=(int *)malloc(sizeof(int)*n);
for(i=1;i<n;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
for(i=1;i<n;i++)
{
//min=lowcost[i];
min=MAX;
k=i;
for(j=1;j<n;j++)
if(lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
mid=closest[k];
printf("(%d,%d)-->",mid,k);
lowcost[k]=MAX;
c[k][mid]=MAX;
for(j=1;j<n;j++)
if(c[k][j]<lowcost[j])
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}