【数据结构】普里母算法和克鲁斯卡尔方法求最小生成树完整程序

#include #include \"stdlib.h\"

#define MaxVertexNum 12 #define MaxEdgeNum 20 #define MaxValue 1000 typedef int VertexType;

typedef VertexType vexlist[MaxVertexNum];

typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; int visited[MaxVertexNum]={0}; struct edgeElem{ int fromvex; int endvex; int weight; };

typedef struct edgeElem edgeset[MaxVertexNum]; void OutputEdgeset(edgeset GE,int e) { int i;

for(i=0;iprintf(\"%d %d %d,\ printf(\"\\n\"); }

void Create3(vexlist GV,edgeset GE,int n ,int e) {

int i,j,k,w;

printf(\"输入%d 个顶点数据\\n\"); for(i=0;iscanf(\" %d\

printf(\"输入%d 条带权边:\\n\"); for(k=0;kscanf(\" %d %d %d\ GE[k].fromvex=i; GE[k].endvex=j; GE[k].endvex=w; } }

void Create1(vexlist GV,adjmatrix GA,int n,int e) {

int i,j,k,w;

printf(\"输入%d 个顶点数据：\\n\"); for(i=0;iif(i==j) GA[i][j]=0;

else GA[i][j]=MaxValue; }

printf(\"输入%d条无向边：\\n\ for(k=1;k<=e;k++)

{scanf(\"%d %d %d\ GA[i][j]=w; } }

void Prim(adjmatrix GA,edgeset CT,int a,int n) {

int i,j,k,min,t,m,w; struct edgeElem x; for(i=0;iif(iCT[i].fromvex=a; CT[i].endvex=i;

CT[i].weight=GA[a][i]; }

else if(i>a) {

CT[i-1].fromvex=a; CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i]; }

}

for(k=1;kmin=MaxValue; m=k-1;

for(j=k-1;jmin=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;it=CT[i].endvex; w=GA[j][t];

if(wCT[i].fromvex=j; } } } }

void Kruskal(edgeset GE,edgeset C,int n) {

int i,j,k,d; int m1,m2; adjmatrix s; for(i=0;ifor(j=0;jwhile(kfor(i=0;iif(1==s[i][GE[d].fromvex]) m1=i; if(1==s[i][GE[d].endvex]) m2=i; }

if(m1!=m2) {

C[k-1]=GE[d]; k++;

for(j=0;js[m1][j] || s[m2][j]; s[m2][j]=0; } } d++; } }

void main() {

int n,e;

vexlist gv; adjmatrix ga; edgeset ge,c;

printf(\"请输入待处理图的顶点数和边数：\\n\"); scanf(\"%d %d\Create1(gv,ga,n,e);

printf(\"利用普利姆算法从顶点0出发求图的最小生成树:\\n\"); Prim(ga,ge,0,n);

OutputEdgeset(ge,n-1);

printf(\" 输入待处理图的顶点数和边数:\"); scanf(\"%d %d\Create3(gv,ge,n,e);

printf(\"利用库鲁斯卡尔算法从顶点0出发求解图的最小生成树：\\n\"); Kruskal(ge,c,n);

OutputEdgeset(c,n-1);

}

// by 更高的飞翔