邻接表（图的一种链式存储结构）

一维数组存储顶点和和其第一个邻接点的指针
单链表存储顶点的所有邻接点
arc：弧（有向图中的边）
edge：边（无向图中的边）
vertex：顶点
adjacent：邻接

图的邻接表存储表示

#define MVNum 100
//单链表中的结点
typedef struct ArcNode{	
	int adjvex;	//顶点的第一邻接点在一维数组中的下标
	struct ArcNode *nextarc;	//指向顶点的下一邻接点
	OtherInfo info;	//边信息，如权值
}ArcNode;	
//顶点（存储在一维数组中）
typedef struct VNode{
	VerTexType data;	//顶点信息
	ArcNode *firstarc;	//顶点的第一邻接点
}VNode,AdjList[MVNum];	//AdjList表示邻接表类型
//邻接表
typedef struct{
	AdjList vertices;	//一维数组vertices
	int vexnum,arcnum;	//图的当前顶点数和边数
}ALGraph;

1.无向图的邻接表结构

Status CreateUDG(ALGraph &G){
	cin >> G.vexnum >> G.arcnum;	//输入总顶点数，总边数
//输入各点，构造一维数组
	for(i=0; i<G.vexnum; ++i){
		cin >> G.vertices[i].data;	//输入顶点值
		G.vertices[i].firstarc=NULL;	//初始化顶点指针域
	}
//输入各边，构造邻接表
	for(k=0; k<G.arcnum; ++k){
		cin >> v1 >> v2;	//输入一条边依附的两个顶点
		i = LocateVex(G,v1);	//确定顶点v1在图G中的位置（一维数组下标）
		j = LocateVex(G,v2);	//确定顶点v2在图G中的位置（一维数组下标）
		
		p1 = new ArcNode;	//生成新结点(指针p1指向该结点，用p1代表该结点)
		p1->adjvex = j;		//邻接点在一维数组中的下标值赋值给该结点
		p1->nextarc = G.vertices[i].firstarc;	
		G.vertices[i].firstarc = p1;	
		
		p2 = new ArcNode;	//生成新结点(指针p2指向该结点，用p2代表该结点)
		p2->adjvex = i;		//邻接点在一维数组中的下标值赋值给该结点
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
	return OK;
}