图论 邻接表表示法

邻接表是图的一种链式存储结构。

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

#define MAX_VERTEX_NUM 20

typedef int InfoType;
typedef int VertexType;
typedef enum{DG,DN,UDG,UDN} GraphKind;

#define Status int 
#define OK 1
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
	//InfoType *info; 该弧相关信息的指针
}ArcNode;
typedef struct VNode
{
	VertexType data;
	ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
	AdjList vertices;
	int vexnum,arcnum;
	GraphKind kind;
}ALGraph;

int LocateVex(ALGraph G,int v)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.vertices[i].data==v)
			return i;
	printf("can not find the data\n");
	exit(1);
}

Status CreateDG(ALGraph &G)
{
	int i,j,k;
	int v1,v2;
	printf("输入该图的顶点数 弧数:\n");
	scanf("%d%d",&G.vexnum,&G.arcnum);
	G.kind=DG;
	printf("输入该图的顶点信息:\n");
	for(i=0;i<G.vexnum;i++)
	{
		scanf("%d",&G.vertices[i].data);
		G.vertices[i].firstarc=NULL;//初始化
	}
	printf("输入该图的弧的相关信息:\n");
	for(k=0;k<G.arcnum;k++)
	{
		scanf("%d%d",&v1,&v2);
		i=LocateVex(G,v1);
		ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));
		p->adjvex=v2;
		p->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p;
	}
	return OK;
}

Status DisplayGraph(ALGraph G)
{
	int i,j;
	for(i=0;i<G.vexnum;i++)
	{
		ArcNode *p=G.vertices[i].firstarc;
		printf("%d",G.vertices[i].data);
		while(p!=NULL)
		{
			printf("--->");
			printf("%d\t",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
	return OK;
}

void main()
{
	ALGraph G;
	CreateDG(G);
	DisplayGraph(G);
}

Graph_theroy

发表评论

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