graph3.c

最小生成树的贪心算法实现 普里姆算法 用邻接矩阵进行图的生成

#include<stdio.h>
#include<malloc.h>

#define MaxVertexNum 100        /*最大顶点数设为100*/
typedef char VertexType;           /*顶点类型设为字符型*/
typedef int EdgeType;              /*边的权值设为整型*/

typedef struct 
{
	VertexType vexs[MaxVertexNum]; /*顶点表*/ // char
    EdgeType edges[MaxVertexNum][MaxVertexNum]; /*邻接矩阵，即边表*/ //int
    int n,e;                       /*顶点数和边数*/
}MGraph;

struct{
	int adjvex;
	int lowcost;
}closedge[MaxVertexNum];

MGraph *G;                  /*MGragh是以邻接矩阵存储的图类型*/
void CreateMGraph(MGraph *G)
{/*建立有向图G的邻接矩阵存储*/
	int i,j,k,weight;
   
	printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    scanf("%d,%d",&(G->n),&(G->e));/*输入顶点数和边数*/
	printf("%d,%d",G->n,G->e);
    printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
	for (i=0;i<G->n;i++)
		scanf("\n%c",&(G->vexs[i]));   /*输入顶点信息，建立顶点表*/
    for (i=0;i<G->n;i++)
		for (j=0;j<G->n;j++)
		{
			G->edges[i][j]=0;             /*初始化邻接矩阵*/
		}
        printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j,weight):\n");
		for (k=0;k<G->e;k++)
		{
			scanf("\n%d,%d,%d",&i,&j,&weight);       /*输入e条边，建立邻接矩阵*/
	        G->edges[i-1][j-1]=weight;/*若加入G->edges[j][i]=1;，*/
			G->edges[j-1][i-1]=weight;
		} /*则为无向图的邻接矩阵存储建立*/
		
}/*CreateMGraph*/

void printg(MGraph *G)
{//采用邻接矩阵输出图
	int i,j;
	printf("打印顶点数和边数:");
	printf("%d,%d\n",G->n,G->e);
	printf("\n");
	
	for(i=0;i<G->n;i++)
		printf("%c ",G->vexs[i]);
	printf(":\n\n");
	for (i=0;i<G->n;i++)
	{
		for (j=0;j<G->n;j++)
			printf("%d ",G->edges[i][j]);
	    printf("\n");
	}
}

void Prim(MGraph *G,int u)
{//采用普里姆算法生成最小生成树
	int v,k,j,min;
	for(v=0;v<G->n;v++)/*初始化，其中<G->n为结点个数*/
		if(v!=u)
		{
			closedge[v].adjvex=u;/*初始时，除u外的顶点其邻接点均假定为u*/
			closedge[v].lowcost=G->edges[u][v];
			/*除u外的每个顶点最小权值边先记为到u的边*/
		}
		closedge[u].lowcost=0;
		/*置顶点u并入U集标记为已找到该顶点最小权值边标志*/
		for(k=0;k<G->n;k++)/*在n个顶点中形成n-1条边的树*/
		{
			min=closedge[k].lowcost;
			v=k;
			for(j=0;j<G->n;j++)
				if((closedge[j].lowcost<min)&&(closedge[j].lowcost!=0))
				{
					min=closedge[j].lowcost;
					v=j;
				}
				printf("%d %d\n",closedge[v].adjvex,v);
				closedge[v].lowcost=0;
				/*顶点v并入U集标并作为已找到该顶点最小权值边标志*/
				for(j=0;j<G->n;j++)/*修改其它顶点边的权值*/
					if(G->edges[v][j]<closedge[j].lowcost)
					{
						closedge[j].lowcost=G->edges[v][j];
						closedge[j].adjvex=v;
					}
		}
}//Prim

void main()
{
	MGraph *tu;
    tu=(MGraph*)malloc(sizeof(MGraph));
	CreateMGraph(tu);
	printg(tu);
	printf("\n");
    Prim(tu,0);
}