数据结构 图论 数组表示法

邻接矩阵表示法:用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息:
代码如下
只写了CreateDN(有向网),CreateUDN(无向网),无向图和无向网类似

源代码:

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

int IncInfo;  //IncInfo为0 则各弧不含其它信息
#define OK 1
#define Status int
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图0,有向网1,无向图2,无向网3}
typedef int VRType; //
typedef int InfoType;
typedef int VertexType;

typedef struct ArcCell
{
     VRType adj;//VRType 是顶点关系类型,对无权图,用1或0表示相邻否;对带权图,则为权值类型
	 InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs[MAX_VERTEX_NUM];
	int vexnum,arcnum;
	GraphKind kind;
}MGraph;

int LocateVex(MGraph G,int v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(v==G.vexs[i])
			return i;
	}
	exit(1);
}
Status CreateDN(MGraph &G)
{
	int i,j,k;
	int v1,v2,w;
	G.kind=DN;
	printf("请输入该 有向网 顶点数,弧数,其他信息");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
	printf("构造顶点向量,分别输入顶点向量\n");
	for(i=0;i<G.vexnum;i++)
		scanf("%d",&G.vexs[i]);
	for(i=0;i<G.vexnum;i++)
	//初始化
	{
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j]->adj=INFINITY;
			G.arcs[i][j]->info=NULL;
		}
	}
	printf("输入一条边依附的顶点以及权值\n");
	for(k=0;k<G.arcnum;k++)
	{
		scanf("%d%d%d",&v1,&v2,&w);
		i=LocateVex(G,v1);j=LocateVex(G,v2);
		G.arcs[i][j]->adj=w;
		if(IncInfo)
			scanf("%d",&G.arcs[i][j]->info);
	}
	return OK;
}
Status CreateUDN(MGraph &G)
{
	int i,j,k;
	int v1,v2,w;
	G.kind=UDN;
	printf("请输入该 无向网 顶点数,弧数,其他信息\n");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
	printf("构造顶点向量,分别输入顶点向量\n");
	for(i=0;i<G.vexnum;i++)
		scanf("%d",&G.vexs[i]);
	for(i=0;i<G.vexnum;i++)
	//初始化
	{
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j]->adj=INFINITY;
			G.arcs[i][j]->info=NULL;
		}
	}
	printf("输入一条边依附的顶点以及权值\n");
	for(k=0;k<G.arcnum;k++)
	{
		scanf("%d%d%d",&v1,&v2,&w);
		i=LocateVex(G,v1);j=LocateVex(G,v2);
		G.arcs[i][j]->adj=w;
		if(IncInfo)
			scanf("%d",&G.arcs[i][j]->info);
		G.arcs[j][i]->adj=G.arcs[i][j]->adj;
	}
	return OK;
}
Status CreateDG(MGraph &G)
{
	return OK;
}
Status CreateUDG(MGraph &G)
{
	return OK;
}
Status display(MGraph G)
{
	int i,j;
	printf("该图的顶点数为%d  弧数为%d\n",G.vexnum,G.arcnum);
	printf("该图的邻接矩阵为:\n");
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
			printf("%d\t",G.arcs[i][j]->adj);
		}
		printf("\n");
	}
	return OK;
}
Status CreateGraph(MGraph &G)
{
	printf("输入需要创建的图的类型 有向图0,有向网1,无向图2,无向网3\n");
	scanf("%d",&G.kind);
	switch(G.kind)
	{
	case DG:return CreateDG(G);
	case DN:return CreateDN(G);
	case UDG:return CreateUDG(G);
	case UDN:return CreateUDN(G);
	default:break;
	}
	return OK;
}
void main()
{
	MGraph G;
	CreateGraph(G);
	display(G);
}



发表评论

邮箱地址不会被公开。 必填项已用*标注