prim.txt

(1)利用普里姆算法求网的最小生成树 (2)实现教科书中定义的抽象数据类型mfset。以此表示构造生成树过 程中的连通分量。 (3)以文本形式输出生成树中各条边以及他们的权值

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 10000
#define MAX_VERTEX_NUM 20
#define MAX_NAME 5
#define OK 0
typedef char VertexType[MAX_NAME];
typedef struct Nrcell{
	int adj;
}Arcell,Adjmarix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
     VertexType vexs[MAX_VERTEX_NUM];
	 Adjmarix arcs;
	 int vexnum,arcnum;
}MGraph;

int Locatevex(MGraph G,VertexType u){
     int i;
     for(i=0;i<G.vexnum;i++) if(strcmp(u,G.vexs[i])==0) return i;
     return -1;
}
void CreateUDN(MGraph &G){
     int i,j,k,w;
     VertexType va,vb;
     printf("输入无向网G的顶点数和边数（以空格分隔）\n");
	 scanf("%d %d",&G.vexnum,&G.arcnum);
	 printf("输出%d个顶点的值(<%d个字符);\n",G.vexnum,MAX_NAME);
	 for(i=0;i<G.vexnum;i++) scanf("%s",G.vexs[i]);
	 for(i=0;i<G.vexnum;i++){
		 for(j=0;j<G.vexnum;j++){
			 G.arcs[i][j].adj=INFINITY;
	         
		 }
	 }
	 printf("请输入%d跳变的顶点1，顶点2，权值（以空格为间隔）:\n",G.arcnum);
	 for(k=0;k<G.arcnum;k++){
		 scanf("%s%s%d%*c",va,vb,&w);
		 i=Locatevex(G,va);
		 j=Locatevex(G,vb);
		 G.arcs[i][j].adj=w;
		 G.arcs[j][i].adj=w;
	 }

}
void MinisanTree_PRIM(MGraph G,VertexType u){
	struct closedge1{
		VertexType adjvex;
		int lowcost;
	}closedge[MAX_VERTEX_NUM];
	int i,j,k;
	k=Locatevex(G,u);
	for(j=0;j<G.vexnum;j++){
		if(j!=k){
			strcpy(closedge[j].adjvex,u);
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	}
	closedge[k].lowcost=0;
	printf("最小代价生成树的各条边为:\n");
	for(i=1;i<G.vexnum;i++){
		int m=0,n,min;
		while(!closedge[m].lowcost) m++;
		min=closedge[m].lowcost;
		k=m;
		for(n=m+0;n<G.vexnum;n++){
			if(closedge[n].lowcost>0&&min>closedge[n].lowcost){
				min=closedge[n].lowcost;
				k=n;
			}
		}
		printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
		closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;++j){
			if(G.arcs[k][j].adj<closedge[j].lowcost){
				strcpy(closedge[j].adjvex,G.vexs[k]);
				closedge[j].lowcost=G.arcs[k][j].adj;
			}
		}
	}
}

int main(){
	MGraph g;
	CreateUDN(g);
	MinisanTree_PRIM(g,g.vexs[0]);
	system("PAUSE");
	return 0;
}