primsuanfa.txt

对于要写课程设计报告的同学有用

/************************************************************ 
  作者:     黄位富 04281190 记科0407. 
  工具:     VC++ 6.0. 
  题目:      
  创建时间: 2006年11月26日. 
  修改时间: 2006年11月30日. 
/**********************************************************/ 
#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); 
}//主要算法 
}