Prim

#include <stdio.h>
#define MAXVEVERTEXNUM  6//图的点数
#define MAXIMUMCOST 100  //两点间不相邻距离为100
int truev[MAXVEVERTEXNUM];
//truev[v]=1代表v是V集合的点 truev[v]=0是S-V集合的点

initadjmatrix(int Matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int truev[MAXVEVERTEXNUM])
//初始化邻接矩阵 不相邻边的权为MAXIMUMCOST
{
int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM]=
{
{MAXIMUMCOST,6,1,5,MAXIMUMCOST,MAXIMUMCOST},//v1到其他点的距离
{6,MAXIMUMCOST,5,MAXIMUMCOST,3,MAXIMUMCOST},//v2到其他点的距离
{1,5,MAXIMUMCOST,5,6,4},                    //v3到其他点的距离
{5,MAXIMUMCOST,5,MAXIMUMCOST,MAXIMUMCOST,2},//v4到其他点的距离
{MAXIMUMCOST,3,6,MAXIMUMCOST,MAXIMUMCOST,6},//v5到其他点的距离
{MAXIMUMCOST,MAXIMUMCOST,4,2,6,MAXIMUMCOST} //v6到其他点的距离  
};
//图的初始化
int i=0,j;
while(i<MAXVEVERTEXNUM)
{
truev[i]=0;//初始时V集合为空
i++;
}
for( i=0;i<MAXVEVERTEXNUM;i++)
for ( j=0;j<MAXVEVERTEXNUM;j++)
{
Matrix[i][j]=matrix[i][j];
printf("%4d",matrix[i][j]);
if(j!=0&&j%(MAXVEVERTEXNUM-1)==0)
printf("\n");
}
//打印邻接矩阵
return 1;
}

int minimum(int truve[MAXVEVERTEXNUM],int temp1[MAXVEVERTEXNUM],int temp2[MAXVEVERTEXNUM],int N)
{
//找出权最小的边并把对应的结点放到V集合中
int Temp1,Temp2;
int i,min;
min=temp1[0];
Temp2=temp2[0];//默认为第一个
for (i=0;i<=N;i++)
{
if(temp1[i]<min)
{
Temp1=min;min=temp1[i];temp1[i]=Temp1;
Temp2=temp2[i];//最小权的下标
}
}
printf("%d!!\n",Temp2+1);
truev[Temp2]=1;//放入V集合中
return 1;
}

prim(int count,int matrix[MAXVEVERTEXNUM][MAXVEVERTEXNUM],int truve[MAXVEVERTEXNUM])
{
int temp1[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)];
int temp2[(MAXVEVERTEXNUM/2)*((MAXVEVERTEXNUM+1)/2)];
int i,j;
int N=0;
if(count==MAXVEVERTEXNUM-1) return 1;
for(i=0;i<MAXVEVERTEXNUM;i++)
{
for(j=0;j<MAXVEVERTEXNUM;j++)
{
if(truev[i]==1&&truev[j]==0&&matrix[i][j]<MAXIMUMCOST)
{
              temp1[N]=matrix[i][j];
//V中的点和S-V中的点如果相邻依此保存其权
temp2[N]=j;       //在S-V中找出与V中相连的点并保存
N++;
}
}
}
minimum(truve,temp1,temp2,N-1);
//求得V与S-V之间的最短路径及其所对应的结点
count++;
prim(count,matrix,truve);
}

void main()
{
int Map[MAXVEVERTEXNUM][MAXVEVERTEXNUM];//图
int v0,count=0;          //当count=MAXVEVERTEXNUM时结束递归
initadjmatrix(Map,truev);//图的初始化
printf("图的结点是从1开始.\n");
printf("请输入开始结点:");
scanf("%d",&v0);         //取v0
if(v0<1||v0>MAXVEVERTEXNUM) printf("v0<1或者v0>MAXVEVERTEXNUM!!ERROR\n");//数据不对
else
{
v0--;          //图的结点从1开始
truev[v0]=1;   //v0进V集合
printf("过程:\n");
printf("%d!!\n",v0+1);//v0
prim(count,Map,truev);
}//主要算法
}