#include "stdio.h"
#define n 6
typedef struct
{
int fromvex,endvex;
float length;
}edge;
edge T[n-1];
float dist[n][n]={{100000,10,100000,100000,19,21},
{10,100000,5,6,100000,11},
{100000,5,100000,6,100000,100000},
{100000,6,6,100000,18,14},
{19,100000,100000,18,100000,33},
{21,11,100000,14,33,100000}};
void Prim(int i)
{
int j,k,m,v;
float min,max=100000;
float d;
edge e;
v=i;
for(j=0;j<=n-2;j++)
{
T[j].fromvex=v;
if(j>=v)
{
T[j].endvex=j+1;
T[j].length=dist[v][j+1];
}
else
{
T[j].endvex=j;
T[j].length=dist[v][j];
}
}
for(k=0;k<n-1;k++)
{
min=max;
for(j=k;j<n-1;j++)
if(T[j].length<min)
{
min=T[j].length;
m=j;
}
e=T[m];
T[m]=T[k];
T[k]=e;
v=T[k].endvex;
for(j=k+1;j<n-1;j++)
{
d=dist[v][T[j].endvex];
if(d<T[j].length)
{
T[j].length=d;
T[j].fromvex=v;
}
}
}
}
int main()
{
int i;
Prim(2);
for(i=0;i<n-1;i++)
{
printf("%d--%.0f-->%d\n",T[i].fromvex,T[i].length,T[i].endvex);
}
return 0;
}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
