一、基本概念
邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图 G 中的每个顶点 vi,将所有邻接于 vi 的顶点 vj 链成一个单链表,这个单链表就称为顶点 vi 的邻接表;再将所有点的邻接表表头放到数组中,就构成了图的邻接表。其中,单链表中的结点称为表结点,每个单链表设的一个头结点称为顶点结点。在邻接表表示中有两种结点结构,如下图所示:
一种是顶点结点结构,它由顶点域(vertex)和指向第一条邻接边的指针域(firstedge)构成;另一种是表结点结构,它由邻接点域(adjvertex)和指向下一条邻接边的指针域(next)构成。对于带权图的边表,需再增设一个存储边上信息(如权值等)的域(info)。带权图的边表结构如下图所示:
下面两张图显示了图与其对应的邻接表表示:
二、 邻接表的实现
#define MaxVertexNum 30 //最大顶点数为30
typedef struct node { //表结点
int adjvertex; //邻接点域,一般是存放顶点对应的序号或在表头向量中的下标
InfoType info; //与边(或弧)相关的信息
struct node *next; //指向下一个邻接点的指针域
} EdgeNode;
typedef struct vnode { //顶点结点
VertexType vertex; //顶点域
EdgeNode *firstedge; //边表头指针
} VertexNode;
//ALGraph 是以邻接表方式存储的图类型
class ALGraph {
public:
void CreateALGraph();
void DFStraverse();
void DFS(int v); //从顶点 v 开始深度遍历算法
void BFS(int v); //从顶点 v 开始广度遍历算法
//其他算法定义略
private:
VertexNode adjlist[MaxVertexNum]; //邻接表
int vertexNum, edgeNum; //顶点数和边数
int visited[MaxVertexNum]; //访问标志数组
};
建立一个有向图的邻接表存储的算法如下:
//建立有向图的邻接表存储,不带边上权值信息的图
void ALGraph::CreateALGraph() {
int i, j, k;
EdgeNode *p;
cout << "请输入顶点数和边数" << endl;
cin >> vertexNum >> edgeNum; //读入顶点数和边数
//建立有 n 个顶点的顶点表
for (i = 0; i < vertexNum; i++) {
cout << "请输入第 " << i << " 个顶点信息:" << endl;
cin >> adjlist[i].vertex; //读入顶点信息
adjlist[i].firstedge=NULL; //顶点的边表头指针设为空
}
cout << "下面输入边表信息:" <<endl;
//建立边表
for(k = 0; k < edgeNum; k++) {
cout << "输入边<i, j>对应的顶点编号i, j" << endl;
cin >> i >> j; //读入边<vi, vj>的顶点对应序号
p = new EdgeNode; //生成新边表结点 p
p->adjvertex = j; //邻接点序号为 j
p->next = adjlist[i].firstedge; //将新边表结点 p 插入顶点 vi 的链表头部
adjlist[i].firstedge=p;
}
}
若无向图中有 n 个顶点、e 条边,则它的邻接表需 n 个头结点和 2e 个表结点。显然,在边稀疏(e<<n(n-1)/2
时)的情况下,用邻接表表示图比邻接矩阵节省存储空间。当和边相关的信息较多时更是如此。
在无向图的邻接表中,顶点 vi 的度恰为第 i 个链表中的结点数;而在有向图中,第 i 个链表中的结点个数只是顶点 vi 的出度,为求入度,必须遍历整个邻接表。在所有链表中,其邻接点域的值为 i 的结点的个数是顶点 vi 的入度。有时,为了便于确定顶点的入度或以顶点 vi 为头的弧,可以建立一个有向图的逆邻接表,即对每个顶点 vi 建立一个链接以 vi 为头的弧的链表。例如,下图所示为有向图 G2(见有向图)的邻接表和逆邻接表。
在建立邻接表或逆邻接表时,若输入的顶点信息为顶点的编号,则建立邻接表的时间复杂度为 O(n+e)
;否则,需要通过查找才能得到顶点在图中的位置,则时间复杂度为 O(n*e)
。 在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点,但要判定任意两个顶点(vi和 vj)之间是否有边或弧相连,则需搜索第 i 个或第 j 个链表,因此不及邻接矩阵方便。