图的存储结构—

图的存储结构——邻接表

作者：追风剑情发布于：2014-8-16 12:06 分类：Algorithms

邻接表是图的一种链式存储结构。所占空间与边数有关，适合存储稀疏图。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。

程序语言 C++
开发工具 Visual Studio2010

#include <stdlib.h>
#include <stdio.h>
 
#define MAXVEX 5	/*图中最大顶点数*/
 
//定义顶点类型为10个字符的字符数组
typedef char VertexType[10];
 
typedef struct edgenode
{
	int adjvex; //邻接点序号
	int value;  //边的权值
	struct edgenode *next; //下一条边的顶点
} ArcNode; //每个顶点建立的单键表中结点的类型
 
typedef struct vexnode
{
	VertexType data; //顶点信息
	ArcNode *firstarc; //指向第一条边结点
} VHeadNode; //单链表的头结点类型
 
typedef struct
{
	int n,e; //n为实际顶点数，e为实际边数
	VHeadNode adjlist[MAXVEX]; //单链表头结点数组
} AdjList; //图的邻接表类型
 
//建立有向图的邻接表
int CreateAdjList(AdjList *&G)
{
	int i,b,t,w;
	ArcNode *p;
	G = (AdjList *)malloc(sizeof(AdjList));
	printf("顶点数(n),边数(e):");
	scanf("%d%d", &G->n, &G->e);
	for(i=0; i<G->n; i++)
	{
		printf("序号为%d的顶点信息：", i);
		scanf("%s", G->adjlist[i].data);
		G->adjlist[i].firstarc = NULL;
	}
 
	for(i=0; i<G->e; i++)
	{
		printf("序号为%d边=>", i);
		printf("起点号 终点号 权值：");
		scanf("%d%d%d", &b, &t, &w);
		if (b<G->n && t<G->n && w>0)
		{
			//建立p结点
			p = (ArcNode *)malloc(sizeof(ArcNode));
			p->value = w;
			p->adjvex = t;
			//插入adjlist[b]单链表之首
			p->next = G->adjlist[b].firstarc;
			G->adjlist[b].firstarc = p;
		}else{
			printf("输入错误!\n");
			return(0);
		}
	}
 
	return(1);
}
 
void DispAdjList(AdjList *G)
{
	int i;
	ArcNode *p;
	printf("图的邻接表表示如下：\n");
	for(i=0; i<G->n; i++)
	{
		printf("[%d, %3s]=>", i, G->adjlist[i].data);
		p = G->adjlist[i].firstarc;
		while(p != NULL)
		{
			printf("(%d, %d)->", p->adjvex, p->value);
			p = p->next;
		}
		printf("NULL\n");
	}
}
 
void main()
{
	AdjList *G;
	CreateAdjList(G);
	DispAdjList(G);
 
	system("pause");
}