图的邻接表表示法：

邻接表(Adjacency List) 是图的 一 种链式存储结构。在邻接表中，对图中每个顶点V建立一个单链表，把与 V相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息， 把这 一 结点看成链表的表头， 其余结点存放有关边的信息， 这样邻接表便由两部分组成：表头结点表和边表。

(1) 表头结点表：由所有表头结点以顺序结构的形式存储， 以便可以随机访问任 一 顶点的边链表。表头结点包括数据域 (data) 和链域 (firstarc) 两部分。其中， 数据域用于存储顶点 V 的名称或其他有关信息；链域用千指向链表中第 一 个结点（即与顶点 V邻接的第 一 个邻接点）。

(2)边表：由表示图中顶点间关系的 2n个边链表组成。边链表中边结点包括邻接点域

(adjvex) 、数据域 (info) 和链域 (nextarc) 三部分。其中， 邻接点域指示与顶点 V邻接的点在图中的位置；数据域存储和边相关的信息， 如权值等；链域指示与顶点v邻接的下 一 条边的结点。

                                                                  表头节点

                                                             边结点

【算法步骤】

1.输入总顶点数和总边数。

2.依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。

3.创建邻接表。依次输入每条边依附的两个顶点， 确定这两个顶点的序号i和j之后， 将此边结点分别插入 Vi 和vj 对应的两个边链表的头部。

//邻接矩阵法构造无向图 
void CreateUGD(ALGraph &G){printf("请输入图的总顶点数:");cin>>G.vexnum;printf("请输入图的总边数:");cin>>G.arcnum;//输入各点，构造表头结点表for(int i=0;i<G.vexnum;i++){printf("请输入第%d个顶点信息:",(i+1));cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;} //输入各边，构造邻接表 for(int k=0;k<G.arcnum;k++){printf("输入第%d条边的信息:\n", (k+1));printf("输入边依附的第一个顶点:");VerTexType v1;cin>>v1;printf("输入边依附的第二个顶点:");VerTexType v2;cin>>v2;//确定v1，v2在图G中的位置，即在G.vertices中的序号int i= LocateVex(G, v1);int j= LocateVex(G, v2);struct ArcNode *p1, *p2;p1=new ArcNode; //生成一个新的边结点 p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;p2=new ArcNode; //生成另一个对称边结点p2 p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
} 

完整的实现代码如下：

#include<stdio.h>
#include<stack> 
#include <iostream>
#define MAXSIZE 100
#define MaxInt 32767 //表示最大值，即正无穷大 
#define MVNum 100 //定义最大顶点数 
using namespace std;typedef char VerTexType; //假设顶点数据类型为字符型
typedef int ArcType; //假设边的权值为整型
//定义边结点 
typedef struct ArcNode{int adjvex;//该边所指向的顶点的位置struct ArcNode *nextarc; //下一条边的指针 
}ArcNode; 
//定义顶点结点信息
typedef struct VNode{VerTexType data;ArcNode *firstarc; //指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum]; 
//定义邻接表的结构
typedef struct {AdjList vertices;int vexnum, arcnum; //当前图的点数和边数 
}ALGraph; //确定顶点vex在G.vertices中的序号
int LocateVex(ALGraph &G, VerTexType vex){for(int i=0;i<G.vexnum;i++){if(G.vertices[i].data==vex){return i;}}
} //邻接矩阵法构造无向图 
void CreateUGD(ALGraph &G){printf("请输入图的总顶点数:");cin>>G.vexnum;printf("请输入图的总边数:");cin>>G.arcnum;//输入各点，构造表头结点表for(int i=0;i<G.vexnum;i++){printf("请输入第%d个顶点信息:",(i+1));cin>>G.vertices[i].data;G.vertices[i].firstarc=NULL;} //输入各边，构造邻接表 for(int k=0;k<G.arcnum;k++){printf("输入第%d条边的信息:\n", (k+1));printf("输入边依附的第一个顶点:");VerTexType v1;cin>>v1;printf("输入边依附的第二个顶点:");VerTexType v2;cin>>v2;//确定v1，v2在图G中的位置，即在G.vertices中的序号int i= LocateVex(G, v1);int j= LocateVex(G, v2);struct ArcNode *p1, *p2;p1=new ArcNode; //生成一个新的边结点 p1->adjvex=j;p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;p2=new ArcNode; //生成另一个对称边结点p2 p2->adjvex=i;p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;}
} //遍历图的邻接表 
void PrintfG(ALGraph &G){printf("遍历图的邻接表:\n");for(int i=0;i<G.vexnum;i++){printf("顶点%c ", G.vertices[i].data);ArcNode *p;p=G.vertices[i].firstarc;while(p){printf("%d ", p->adjvex);p=p->nextarc;}}
}int main(){ALGraph G;CreateUGD(G);PrintfG(G);
}