prim算法求最小生成树
#include<stdio.h>#include<stdlib.h>
#define M 20
typedef char datatype;
typedef struct node{
int adjvex;
truct node *next;
}EdgeNode;
typedef struct vnode{
datatype vertex;
EdgeNode *FirstEdge;
}VertexNode;
typedef struct{
VertexNode adjlist[M];
int n,e;
}linkedGraph;
typedef struct edgedata{
int beg,en;
int length;
}edge;
voide prim(Mgraph t,edge tree[M-1])
{
edge x;
int d,min,j,k,s,v;
for(v=1;v<=g.n;v++)
{
tree[v-1].beg=0;
tree[v-1].en=v;
tree[v-1].length=g.edges[0][v];
}
for(k=0;k<=g.n-3;k++)————————————这里为什么是k<=g.n-3
{
min=tree[k].length;
s=k;
for(j=k+1;j<=g.n-2;j++)
if(tree[j].length<min)
{
min=tree[j].length;
s=j;
}
v=tree[s].en;
x=tree[s];tree[s]=tree[k];
tree[k]=x;
for(j=k+1;j<=g.n-2;j++)_______________这里为什么是k<=g.n-2
{
d=g.edgex[v][tree[j].en];
if(d<tree[j].length;
{
tree[j].length=d;
tree[j].beg=v;
}
}
}
printf("\n the minimum cost spanning tree is:\n");
for(j=0;j<=g.n-2;j++)
printf("\n%c---%c %d\n",g.vex[tree[j].beg],g.vexs[tree[j].en],ree[j].length);
pritf("\n the root of it is %c\n",g.vexs[0]);
}
void main()
{
Mgraph g;
edge tree[M-1];
char filename[20];
printf("please input filename of Graph:\n");
gets(filename);
great(&g,filename,0);
prim(g,tree);
}
