作者：解学武

邻接表（Adjacency List）是图的一种链式存储结构，既可以存储无向图（网），也可以存储有向图（网）。

邻接表存储图的核心思想是：将图中的所有顶点存储到顺序表中（也可以是链表），同时为各个顶点配备一个单链表，用来存储和当前顶点有直接关联的边或者弧（边的一端是该顶点或者弧的弧尾是该顶点）。

举个简单的例子，下图是一张有向图和它对应的邻接表：


以顶点 V1 为例，它对应的单链表中有两个结点，存储的值分别是 2 和 1。2 是 V3 顶点在顺序表中的位置下标，存储 2 的结点就表示 <V1, V3> 这条弧；同理，1 是 V2 顶点在顺序表中的位置下标，存储 1 的结点就表示 <V1, V2> 这条弧。

也就是说，邻接表中存储边或弧的方法，就是存储边或弧另一端顶点在顺序表中的位置下标。

继续分析图 1b) 中的另外 3 个单链表：

• V2：由于图中不存在以 V2 为弧尾的弧，所以不需要为 V2 构建链表；
• V3：以 V3 为弧尾的弧只有 <V3, V4>，V4 在顺序表对应的下标为 3，因此单链表中只有 1 个结点，结点中存储 3 来表示 <V3, V4>。
• V4：以 V4 为弧尾的弧只有 <V4, V1>，V1 在顺序表对应的下标为 0，因此单链表中只有 1 个结点，结点中存储 0 来表示 <V4, V1>。

邻接表的具体实现

实际上，邻接表就是由一个顺序表和多个单链表组成的，顺序表用来存储图中的所有顶点，各个单链表存储和当前顶点有直接关联的边或弧。

存储顶点的顺序表，内部各个空间的结构如下图所示：


data 为数据域，用来存储各个顶点的信息；next 为指针域，用来链接下一个结点。

对于无向图或者有向图来说，单链表中存储边或弧的结点也可以用图 2 所示的结构来表示，data 数据域存储边或弧另一端顶点在顺序表中的下标，next 指针域用来链接下一个结点。对于无向网或者有向网来说，结点可以用下图所示的结构来表示：


adjvex 数据域用来存储边或弧另一端顶点在顺序表中的下标；next 指针域用来链接下一个结点；info 指针域用来存储有关边或弧的其它信息，比如边或弧的权值。

用 C 语言表示邻接表的实现代码如下：

#define  MAX_VERTEX_NUM 20//图中顶点的最大数量
#define  VertexType int//图中顶点的类型
#define  InfoType int*//图中弧或者边包含的信息的类型
typedef struct ArcNode{
    int adjvex;//存储边或弧，即另一端顶点在数组中的下标
    struct ArcNode * nextarc;//指向下一个结点
    InfoType info;//记录边或弧的其它信息
}ArcNode;
typedef struct VNode{
    VertexType data;//顶点的数据域
    ArcNode * firstarc;//指向下一个结点
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表首元结点的数组
typedef struct {
    AdjList vertices;//存储图的邻接表
    int vexnum,arcnum;//记录图中顶点数以及边或弧数
    int kind;//记录图的种类
}ALGraph;

以上各个结构体中的成员并非一成不变，根据实际场景的需要，可以修改它们的数据类型，还可以适当地删减。

邻接表计算顶点的出度和入度

在有向图（网）中，顶点的入度指的是以当前顶点一端为弧头的弧的数量；顶点的出度指的是以当前顶点一端为弧尾的弧的数量。

例如，图 1a) 中顶点 V1 的入度为 1，出度为 2。

在邻接表中计算某个顶点的出度是非常简单的，只需要在顺序表中找到该顶点，然后计算该顶点所在链表中其它结点的数量，即为该顶点的出度。例如，图 1b) 中为 V1 构建的链表中有 2 个结点，因此 V1 的出度就是 2。

在邻接表中计算某个顶点的入度，有两种实现方案：

1. 遍历顺序表，找到该顶点，获取该顶点所在顺序表中的下标（假设为 K）。然后遍历所有单链表中的结点，统计数据域为 K 的结点数量，即为该顶点的入度。
2. 建立一个逆邻接表，表中各个顶点的链表中记录的是以当前顶点一端为弧头的弧的信息。比如说，图 1a) 对应的逆邻接表如下图所示：

以 V1 顶点为例，数据域为 3 的结点记录的是 <V4, V1> 这条弧。

总结

对于具有 n 个顶点和 e 条边的无向图，邻接表中需要构建 n 个首元结点和 2e 个表示边的结点；对于具有 n 个顶点和 e 条弧的有向图，邻接表需要构建 n 个首元结点和 e 个表示弧的结点。

当图中边或者弧稀疏时，用邻接表比前一节介绍的邻接矩阵更加节省空间，边或弧相关信息较多时更是如此。

最后，用邻接表存储图 1a) 中有向图的 C 语言程序如下所示：

#include<stdio.h>
#include<stdlib.h>
#define  MAX_VERTEX_NUM 20//最大顶点个数
#define  VertexType char//图中顶点的类型

typedef struct ArcNode {
    int adjvex;//存储弧，即另一端顶点在数组中的下标
    struct ArcNode* nextarc;//指向下一个结点
}ArcNode;

typedef struct VNode {
    VertexType data;//顶点的数据域
    ArcNode* firstarc;//指向下一个结点
}VNode, AdjList[MAX_VERTEX_NUM];//存储各链表首元结点的数组

typedef struct {
    AdjList vertices;  //存储图的邻接表
    int vexnum, arcnum;//图中顶点数以及弧数
}ALGraph;

void CreateGraph(ALGraph * graph) {
    int i, j;
    char VA, VB;
    ArcNode* node = NULL;
    printf("输入顶点的数目：\n");
    scanf("%d", &(graph->vexnum));
    printf("输入弧的数目：\n");
    scanf("%d", &(graph->arcnum));
    scanf("%*[^\n]"); scanf("%*c");
    printf("输入各个顶点的值：\n");
    for (i = 0; i < graph->vexnum; i++) {
        scanf("%c", &(graph->vertices[i].data));
        getchar();
        graph->vertices[i].firstarc = NULL;
    }
    //输入弧的信息，并为弧建立结点，链接到对应的链表上
    for (i = 0; i < graph->arcnum; i++) {
        printf("输入弧(a b 表示弧 a->b)：\n");
        scanf("%c %c", &VA, &VB);
        getchar();
        node = (ArcNode*)malloc(sizeof(ArcNode));
        node->adjvex = '#';
        node->nextarc = NULL;
        //存储弧另一端顶点所在顺序表中的下标
        for (j = 0; j < graph->vexnum; j++) {
            if (VB == graph->vertices[j].data) {
                node->adjvex = j;
                break;
            }
        }
        //如果未在顺序表中找到另一端顶点，则构建图失败
        if (node->adjvex == '#') {
            printf("弧信息输入有误\n");
            exit(0);
        }
        //将结点添加到对应的链表中
        for (j = 0; j < graph->vexnum; j++) {
            if (VA == graph->vertices[j].data) {
                //将 node 结点以头插法的方式添加到相应链表中
                node->nextarc = graph->vertices[j].firstarc;
                graph->vertices[j].firstarc = node;
                break;
            }
        }
        if (j == graph->vexnum) {
            printf("弧信息输入有误\n");
            exit(0);
        }
    }
}

//计算某个顶点的入度
int InDegree(ALGraph graph, char V) {
    int i, j, index = -1;
    int count = 0;
    //找到 V 在顺序表中的下标
    for (j = 0; j < graph.vexnum; j++) {
        if (V == graph.vertices[j].data) {
            index = j;
            break;
        }
    }
    if (index == -1) {
        return -1;
    }
    //遍历每个单链表，找到存储 V 下标的结点，并计数
    for (j = 0; j < graph.vexnum; j++) {
        ArcNode* p = graph.vertices[j].firstarc;
        while (p) {
            if (p->adjvex == index) {
                count++;
            }
            p = p->nextarc;
        }
    }
    return count;
}

//计算某个顶点的出度
int OutDegree(ALGraph graph, char V) {
    int j;
    int count = 0;
    for (j = 0; j < graph.vexnum; j++) {
        if (V == graph.vertices[j].data) {
            ArcNode* p = graph.vertices[j].firstarc;
            while (p) {
                count++;
                p = p->nextarc;
            }
            break;
        }
    }
    //如果查找失败，返回 -1 表示计算失败
    if (j == graph.vexnum) {
        return -1;
    }
    return count;
}

int main(void) {
    ALGraph graph;
    CreateGraph(&graph);
    if (OutDegree(graph, 'A') != -1) {
        printf("%c 顶点的出度为 %d\n", 'A', OutDegree(graph, 'A'));
    }
    if (InDegree(graph, 'A') != -1) {
        printf("%c 顶点的入度为 %d", 'A', InDegree(graph, 'A'));
    }
    return 0;
}

假设我们用 A、B、C、D 分别表示 V1、V2、V3、V4，程序的执行过程为：

输入顶点的数目：
4
输入弧的数目：
4
输入各个顶点的值：
A B C D
输入弧(a b 表示弧 a->b)：
A B
输入弧(a b 表示弧 a->b)：
A C
输入弧(a b 表示弧 a->b)：
C D
输入弧(a b 表示弧 a->b)：
D A
A 顶点的出度为 2
A 顶点的入度为 1