net.cpp

计算出N各城市间的最小生成树,用c语言实现

#include"stdafx.h"
#include<stdio.h>
#define max 555
#define maxvex 20
typedef struct {
	char vexs[maxvex];
	int adjmatrix[maxvex][maxvex];
	int vexnum,arcnum;
}MGraph;
struct clo{
	char adjvex;
	int lowcost;
};
struct clo closedge[maxvex];
int locatevex(MGraph G,char v)
{int i;
	for(i=0;i<G.vexnum;i++)
		{if(G.vexs[i]==v) break;}
	return i;}
void CreateUDN(MGraph &G){
	int i,j,k;char v1,v2;int w;char enterkey;
	printf("请输入顶点和边的个数，用逗号隔开:");
	scanf("%d,%d%c",&G.vexnum,&G.arcnum,&enterkey);
	printf("请依次输入每一个顶点的名称，用大写字母如A,B表示:\n");
	for(i=0;i<G.vexnum;i++)  scanf("%c%c",&G.vexs[i],&enterkey);
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++) G.adjmatrix[i][j]=max;
	for(k=0;k<G.arcnum;k++){
		printf("请输入每一条边的两个顶点的名称和权值:\n");
		scanf("%c%c",&v1,&enterkey);
		scanf("%c%c",&v2,&enterkey);
		scanf("%d%c",&w,&enterkey);
		i=locatevex(G,v1);j=locatevex(G,v2);
		G.adjmatrix[i][j]=w;
		G.adjmatrix[j][i]=G.adjmatrix[i][j];}
	}
int mininum(struct clo a[maxvex],int n)
{	int i,p=0,value=max;
	for(i=0;i<n;i++)
		if(a[i].lowcost<value && a[i].lowcost!=0) {
			value=a[i].lowcost;
			p=i;}
	return p;

}
void minispantree_prim(MGraph G,char u)
{	int i,k,j;
	k=locatevex(G,u);
for(j=0;j<G.vexnum;j++)
		if(j!=k){ 
			closedge[j].adjvex=u; closedge[j].lowcost=G.adjmatrix[k][j];}
		closedge[k].lowcost=0;

		for(i=1;i<G.vexnum;i++){
			k=mininum(closedge,G.vexnum);
			printf("%-3c,%3c",closedge[k].adjvex,G.vexs[k]);
			printf("\n");
			closedge[k].lowcost=0;

			for(j=0;j<G.vexnum;j++)
				if(G.adjmatrix[k][j]<closedge[j].lowcost){
					closedge[j].adjvex=G.vexs[k];
					closedge[j].lowcost=G.adjmatrix[k][j];}
		}}
int main()
{
	MGraph G;char v;
	printf("本次实验是关于n个城市间最小生成树的问题\n");
	CreateUDN(G);
	printf("本次实验中，图的存储结构采用邻接矩阵的存储方式，该矩阵为(555表示权值不存在):\n"); 
	for(int i=0;i<G.vexnum;i++){
	for(int j=0;j<G.vexnum;j++)
	printf("%-6d",G.adjmatrix[i][j]);
	printf("\n");}
	printf("请输入最小生成树的第一个顶点，用大写字母表示:\n");
	scanf("%c",&v);
	printf("构造出的最小生成树的边如下:\n");
	minispantree_prim(G,v);

	return 0;
}