mgraph.h

最少生成树问题

#include "stdio.h"
#include "stdlib.h"

#define MAX_VERTEX_NUM 30			//图的最大节点数


typedef char VERTEXTYPE;	//定义图的节点类型

typedef struct ArcCell	// 弧的定义
{ 
	int adj;			// 对无权图，用1或0表示相邻否；对带权图，则为权值类型。
    //InfoType *info;		// 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct // 图的定义
{  
	VERTEXTYPE  vexs[MAX_VERTEX_NUM];       // 顶点信息
    AdjMatrix  arcs;		// 弧的信息                     
    int  vexnum, arcnum;	// 顶点数，弧数             
} MGraph;

int LocateVex(MGraph G, VERTEXTYPE v)
{
	int locate=0;
	while( G.vexs[locate]!=v && locate<G.vexnum )locate++;
	if(locate==G.vexnum)
	{
		printf("该节点不存在！\n");
		return(locate);
	}
	else return(locate);
}

void CreateUDN(MGraph &G)      //建无向网的邻接矩阵表示
{
	int i,j,k,w;
	VERTEXTYPE v1,v2;
	printf("请输入图中节点和弧的个数，中间以逗号间隔：\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	getchar();	//用来接收回车符
	printf("请输入节点向量，中间不需要间隔：\n");
	for( i=0; i<G.vexnum; i++ ) G.vexs[i]=getchar();	//构造顶点向量
	getchar();	//用来接收回车符
	//for( i=0; i<G.vexnum; i++ ) printf("%c",G.vexs[i]);
	for( i=0; i<G.vexnum; i++ )
       for( j=0; j<G.vexnum; j++ ) G.arcs[i][j].adj=1000;	//初始化邻接矩阵,1000表示最大权值
	printf("请输入每条边依附的顶点和权值，中间以逗号间隔：\n");
	for( k=0; k<G.arcnum; k++ )
    { 
		scanf("%c,%c,%d",&v1,&v2,&w);		//输入一条边依附的顶点和边的权值
		getchar();	//用来接收回车符
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
        G.arcs[i][j].adj=w;			//修改邻接矩阵
		G.arcs[j][i].adj=w;			//修改邻接矩阵
	}
}//   时间复杂度为O(n2)

typedef struct
{
	VERTEXTYPE adjvex;
	int lowcost;
}Closedge[MAX_VERTEX_NUM];

Closedge closedge;

int minimum(Closedge closedge,MGraph G)
{
	int i=0, m=1000;		//先规定1000为最大权值
	for( int j=0; j<G.vexnum; j++ )
		if(closedge[j].lowcost>0)
			if(closedge[j].lowcost<m)
			{
				m=closedge[j].lowcost;
				i=j;
			}
	return(i);
}

void MiniSpanTree_P(MGraph G, VERTEXTYPE u)		//用普里姆算法从顶点u出发构造网G的最小生成树
{ 
	int k = LocateVex( G, u ); 
	for( int 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;      //初始，U＝{u}
	for (int i=1; i<G.vexnum; i++) 
	{
		k = minimum(closedge,G);	//求出加入生成树的下一个顶点(k)                  
		printf("%c%c\n",closedge[k].adjvex, G.vexs[k]);	// 输出生成树上一条边 
		closedge[k].lowcost = 0;	// 第k顶点并入U集
		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;
		}
	}//for
}