primtraverse.c

来自「1、 图的存储结构的定义和图的创建 图的种类有：有向图、无向图、有向网、无向网」· C语言 代码 · 共 95 行

#include"mgraph.h"

int Locate(MGraph G,char v)
{
	int i;
	for(i=0;i<G.vexnum&&G.vexs[i]!=v;i++);
	return i;
}

void CreatUDN(MGraph *G){
	int i,j,k,w;
	char v1,v2;
	printf("input arcnum and vexnum\n");
	scanf("%d %d",&(*G).arcnum,&(*G).vexnum);
	getchar();
	for(i=0;i<(*G).vexnum;i++)
	{
		printf("input vex\n");
		scanf("%c",&(*G).vexs[i]);
		getchar();
		printf("%c%d",(*G).vexs[i],i);
	}
	for(i=0;i<(*G).vexnum;i++)
		for(j=0;j<(*G).vexnum;j++)
			(*G).arcs[i][j].adj=INFINITY;
	for(k=0;k<(*G).arcnum;k++)
	{
		printf("input edge and w\n");
		scanf("%c%c%d",&v1,&v2,&w);
		getchar();
		printf("%c%c%d\n",v1,v2,w);
		i=Locate((*G),v1);
		j=Locate((*G),v2);
		printf("%d%d",i,j);
		(*G).arcs[i][j].adj=w;
		(*G).arcs[j][i].adj=w;
	}
}

int minimum(closedge closedge,MGraph G)
{
	int k,min=INFINITY,j=0;
	for(k=0;k<G.vexnum;k++)
		if(closedge[k].lowcost>0&&min>closedge[k].lowcost)
		{
			min=closedge[k].lowcost;
			j=k;
		}
	return j;
}



void MiniSpanTree_PRIM(MGraph G,char u)
{
	int k,i,j;
	closedge closedge;
	k=Locate(G,u);
	printf("%d\n",k);
	for(j=0;j<G.vexnum;j++)
		if(j!=k)
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
	closedge[k].lowcost=0;
	for(i=1;i<G.vexnum;++i)
	{
		k=minimum(closedge,G);
		//printf("%d\n",k);
		printf("%c%c,",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)
			{
				closedge[j].adjvex=G.vexs[k];
				closedge[j].lowcost=G.arcs[k][j].adj;
			}
	}
}

main()
{ 
	MGraph G;
	char u;
	CreatUDN(&G);
	u=G.vexs[0];
	printf("%c\n",u);
	MiniSpanTree_PRIM(G,u);
}