普里姆最小树.cpp

来自「数据结构中关于图的操作,含多种操作方法例子」· C++ 代码 · 共 90 行

#include"lj.h"
#define N 3
struct cd {
	char adjvex;
	int lowcost;
}closedge[N];

int locatevex(adjmax g,char u,int n);
int mininum(struct cd cloed[N],int n);

void main()
{
	int i,j,k,w,n,e;
	char b,t;
	adjmax adj;
	printf("输入顶点数(n)和边数(e):  ");
	scanf("%d%d",&n,&e);
	for(i=1;i<=N;i++)
	{
		getchar();
		printf("  第%d个顶点的信息:  ",i);
		scanf("%c",&adj.vexs[i]);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=30;
	for(k=1;k<=e;k++)
	{
		getchar();
		printf("第%d条边:  ",k);
		b=getchar();
		t=getchar();
		getchar();
		i=locatevex(adj,b,n);
		j=locatevex(adj,t,n);
		printf(" 权值:  ");
		scanf("%d",&w);
		adj.edges[i][j]=adj.edges[j][i]=w;
	}
	printf("该图对应的邻接矩阵为:\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj.edges[i][j]);
		printf("\n");
	}
//	char u;
//	u=adj.vexs[1];
	k=locatevex(adj,adj.vexs[1],n);
	for(j=1;j<=n;j++)
	{
		if(j!=k)	
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=adj.edges[k][j];
		}
		closedge[k].lowcost=0;
		for(i=1;i<=n;i++)
		{
			k=mininum(closedge,n);
			printf("%4c%4c\n",closedge[j].adjvex,adj.vexs[k]);
			closedge[k].lowcost=0;
			for(j=1;j<=n;j++)
				if(adj.edges[k][j]<closedge[j].lowcost)
				{
					closedge[j].adjvex=adj.vexs[k];
					closedge[j].lowcost=adj.edges[k][j];
				}
		}
	}
}

int mininum(struct cd cloed[N],int n)
{
	int i,t=30;
	for(i=2;i<=n;i++)
		if(t<cloed[i].lowcost)
			t=cloed[i].lowcost;
		return t;
}


int locatevex(adjmax g,char u,int n)
{
	int i;
	for(i=1;i<=n;i++)
		if(g.vexs[i]==u)
			return i;
		return 0;
}