学步园

邻接表

邻接表法是图的链式存储方式,它包括表头节点表和边表;表头节点表存储图的各个顶点,每个节点由两部分组成:数据域(存储顶点的名称和其他数据)和链域(指向第一个邻接点);

C语言表述形式:

#define MAX_VERTEX_NUM 20					//最多顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKing;		//图的种类

/*边表中节点的数据结构*/
typedef struct ArcNode{
	int adjvex;								//该弧指向顶点的位置
	struct ArcNode * nextarc;				//指向下一条弧的指针
	/*可添加其他信息*/
}ArcNode;

/*表头节点表中节点的数据结构*/
typedef struct VertexNode{
	VertexData data;						//顶点数据
	ArcNode *firstarc;						//指向该顶点的第一条弧的指针
}VertexNode;

typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];
	int vexnum,arcnum;						//图的顶点数目和弧数目
	GraphKing king;							//图的种类
}AdjList;

下面给出测试代码:

/*建立无向图为例*/

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20					//最多顶点个数
typedef int VertexData;
typedef enum{DG,DN,UDG,UDN} GraphKing;		//图的种类

/*边表中节点的数据结构*/
typedef struct ArcNode{
	int adjvex;								//该弧指向顶点的位置
	struct ArcNode * nextarc;				//指向下一条弧的指针
	/*可添加其他信息*/
}ArcNode;

/*表头节点表中节点的数据结构*/
typedef struct VertexNode{
	VertexData data;						//顶点数据
	ArcNode *firstarc;						//指向该顶点的第一条弧的指针
}VertexNode;

typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];
	int vexnum,arcnum;						//图的顶点数目和弧数目
	GraphKing king;							//图的种类
}AdjList;

/*寻找数据v在表头节点表的位置*/
int Locate(AdjList *G,VertexData v)
{
	int j=-1,k;
	for(j=1;j<=G->vexnum;j++){
		if(G->vertex[j].data == v)
		{
			k = j;
			break;
		}
	}
	return j;
}

void CreateAdjList(AdjList *G)
{
	int i,k;
	int ch1,ch2;
	ArcNode *s,*p;

	printf("输入顶点个数及弧的条数:\n");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	printf("输入各个顶点\n");
	for(i=1;i<=G->vexnum;i++){
		scanf("%d",&G->vertex[i].data);
	}

	for(i=1;i<=G->vexnum;i++){				//从数组的第二位开始
		G->vertex[i].firstarc = NULL;
	}

	printf("输入弧的两个顶点\n");
	for(i=1;i<=G->arcnum;i++){
		printf("输入%d条弧数据:\n",i);
		scanf("%d%d",&ch1,&ch2);
		s = (ArcNode*)malloc(sizeof(ArcNode));
		
		//建立于顶点ch1相关的弧
		k = Locate(G,ch1);
		//printf("k = %d\n",k);
		s->adjvex = ch2;
		s->nextarc = G->vertex[k].firstarc;
		G->vertex[k].firstarc = s;
		
		//建立与顶点ch2相关的弧
		p = (ArcNode*)malloc(sizeof(ArcNode));
		k = Locate(G,ch2);
		//printf("k = %d\n",k);
		p->adjvex = ch1;
		p->nextarc = G->vertex[k].firstarc;
		G->vertex[k].firstarc = p;
	}

}

/*打印*/
void PrintAdjList(AdjList *G)
{
	int i;
	ArcNode *p;
	for(i=1;i<=G->vexnum;i++){
		p = G->vertex[i].firstarc;
		printf("于顶点%d相关的弧:  ",G->vertex[i].data);
		while(p != NULL){
			printf("%d ",p->adjvex);
			p = p->nextarc;
		}
		printf("\n");
	}
}
int main()
{
	AdjList G;
	CreateAdjList(&G);
	PrintAdjList(&G);
	return 0;
}

和邻接表对应的有逆邻接表，其主要区别为各个边或弧的adjvex存储的是指向该顶点的位置(对于有向图)