分别利用prim算法和kruskal算法实现求图的最小生成树.doc
文本预览下载声明
/*分别利用prim算法和kruskal算法实现求图的最小生成树*/
#includestdio.h
#includestdlib.h
#define MaxVertexNum 12
#define MaxEdgeNum 20
#define MaxValue 1000
typedef int Vertextype;
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];
typedef Vertextype vexlist[MaxVertexNum];
int visited[MaxVertexNum]={0};
struct edgeElem
{int fromvex;
int endvex;
int weight;
};
typedef struct edgeElem edgeset[MaxVertexNum];
void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)
{int i,j,k,w;
printf(输入%d个顶点数据,n);
for(i=0;in;i++)
?? scanf(%d,GV[i]);
for(i=0;in;i++)
?? for(j=0;jn;j++)
??????? if(i==j) GA[i][j]=0;
???????? else GA[i][j]=MaxValue;
printf(输入%d条无向带权边,e);
for(k=0;ke;k++)
{
scanf(%d%d%d,i,j,w);
GA[i][j]=GA[j][i]=w;
}
}
void Creat_edgeset(vexlist GV,edgeset GE,int n,int e)
{int i,j,k,w;
printf(输入%d个顶点数据,n);
for(i=0;in;i++)
?? scanf(%d,GV[i]);
printf(输入%d条无向带权边,e);
for(k=0;ke;k++)
{ scanf(%d%d%d,i,j,w);
?? GE[k].fromvex=i;
?? GE[k].endvex=j;
?? GE[k].weight=w;
}
}
void output_edgeset(edgeset GE,int e)
{int k;
for(k=0;ke;k++)
printf(%d %d %d,,GE[k].fromvex,GE[k].endvex,GE[k].weight);
printf(\n);
}
void prim(adjmatrix GA,edgeset CT,int a,int n)
{int i,j,t,k,w,min,m;
struct edgeElem x;
for(i=0;in;i++)
if(ia)
?? {CT[i].fromvex=a;
??? CT[i].endvex=i;
??? CT[i].weight=GA[a][i];
?? }
else if(ia)
?? {CT[i-1].fromvex=a;
??? CT[i-1].endvex=i;
??? CT[i-1].weight=GA[a][i];
??? }
for(k=1;kn;k++)
{
??? min=MaxValue;
??? m=k-1;
??? for(j=k-1;jn-1;j++)
????? if(CT[j].weightmin){min=CT[j].weight;m=j;}
????? x=CT[k-1];CT[k-1]=CT[m];CT[m]=x;
??? j=CT[k-1].endvex;
?? for(i=k;in-1;i++)
{t=CT[i].endvex;w=GA[j][t];
?? if(wCT[i].weight)
???? {CT[i].weight=w;
????? CT[i].fromvex=j;
????? }
??? }
}
}
void kruskal(edgeset GE,edgeset C,int n)
{ int i,j,k,d;
??? int m1,m2;
??? adjmatrix s;
for(i=0;in;i++)
??? {for(j=0;jn;j++)
?????? if(i==j) s[i][j]=1;else s[i][j]=0;
???? }
k=1;
d=0;
while(kn)
{
for(i=0;in;i++)
?? {if(s[i][GE[d].fromvex]==1) m1=i;
??? if(s[i][GE[d].endvex]==1) m2=i;
}
if(m1!=m2)
{C[k-1]=GE[d];k++;
for(j=0;j
显示全部