邻接表是图的一种链式储存结构。
在边数小于节点数的图中，如果继续使用邻接矩阵，那么就会造成资源浪费。比如我们有一个有图，一共五个节点，却只有4 条边，生成5*5的邻接矩阵时，此时在这25个内存空间中只有4个被有效的利用，这就造成了浪费。
这时，我们可以联想到链式结构。在前面的知识中，可以知道，链表相对与数组可以更有效的利用起内存空间，避免资源浪费。
因为链表是动态的，大小不用事先确定。
那么我们怎么用链表来表示图的呢？
在图中（下面说的图都为无向图），每个节点都会与一个或者多个节点连接，我们为每一个节点创建一个链表，以储存他们所连接的节点，可是我们知道，节点的next指针只能有一个，如果一个节点与多个节点连接，就会出现指针不够用的情况。为了解决这个问题，我们可以先建立一个结构体数组储存节点，再建立一个链表储存每个节点指向其他节点所在数组的下标。在结构体数组中，每个数组元素都包含着一个链表。如下图所示：
#include<iostream> using namespace std; const int MAXNUM = 100; typedef int DATETYPE; typedef struct ArcNode { int adjvex; //顶点下标，该边所指向的节点的位置 struct ArcNode *next; //指向下一边的指针 int info; //改边的相关信息（如权值），用的不多 }ArcNode; typedef struct VextexNode { DATETYPE date; //顶点信息 ArcNode *firstarc;//指向第一条边的指针 }VextexNode; typedef struct AdjListGraph { VextexNode adjlist[MAXNUM];//邻接表 int NumNodes, NumEdges;//顶点数和边数 }AdjListGraph; void Create(AdjListGraph &G) { int i, j, k; ArcNode *pev; cout << "请输入邻接表的顶点数以及边数（空格隔开）：" << endl; cin >> G.NumNodes >> G.NumEdges; cout << "请输入每个顶点的值(回车)：" << endl; for (i = 0; i < G.NumNodes; ++i) { cin >> G.adjlist[i].date; G.adjlist[i].firstarc = NULL; } for (k = 0; k< G.NumEdges; ++k){ cout << "输入边(vi,vj)的顶点序号i,j（空格分隔）："; cin >> i >> j; if (!(pev = (ArcNode *)malloc(sizeof(ArcNode)))) return; pev->adjvex = j;//邻接序号为j pev->next = G.adjlist[i].firstarc;//将pev指向当前顶点指向的顶点 G.adjlist[i].firstarc = pev; /*由于是无向的边，故将对j的操作对i进行一次*/ if (!(pev = (ArcNode *)malloc(sizeof(ArcNode)))) return; pev->adjvex = i; pev->next = G.adjlist[j].firstarc; G.adjlist[j].firstarc = pev; } } void main() { AdjListGraph G; Create(G); system("pause"); }
