前置知识:

  1. 链表

  2. 指针数组

概述

邻接表本质上是一个二维链表(线性表)

邻接表存储了与每一个顶点相邻的边集的集合.换句话说,邻接表由若干个链表组成,每个链表都对应图中一个顶点,存储以该顶点为起点的边集.

其中每一个链表就称为该顶点的邻接表,所有的这些链表共同组成这个图的邻接表.

例如对该图建立邻接表:

image-20231229213940793

左边为一个指针数组,存储每个链表的头指针(即第一个结点的指针),右边则为对应的邻接表,存储各个边:

image-20231229213925777

以顶点A为例,<A,B,3>为其第一条出边,<A,C,1>为第二条出边,这2条边作为2个表项组成A的邻接表(链表).

所以邻接表是用来存储每个节点的出边集合的数据结构.

另外,由于树也是一种特殊的图(没有回路的图),因此邻接表也可以用于存储树.

优缺点

优点:

  1. 节省空间

    与一般的邻接矩阵相比较而言,邻接表更节省空间.

    邻接表只关注存在的边,忽略了邻接矩阵中不存在的边(为0的元素),空间复杂度为O(n+m),n,m分别为顶点数和边数,即需要一个长度为n的表头,所有的链表共有m个结点存储m条边.

    因此,邻接表很适合存储稀疏图.

  2. 方便遍历某个顶点的所有邻接点—出边

    因此很适合作为求解单源最短路径等问题的存储结构.

缺点

  1. 确定2点间的边信息需要遍历2个链表.

  2. 存向图时,删除一条边需要从2个链表中进行2次删除.

  3. 当需要了解某个顶点的入度时,比如拓扑排序,需要遍历整个邻接表.—当然也有解决办法,那就是逆邻接表–存储每个节点的入边的集合.

    或者使用十字链表来同时存储图的入度和出度信息.

代码实现

使用C语言实现邻接表的ADT.

AdjacencyList.h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#ifndef ADJACENCYLIST_H
#define ADJACENCYLIST_H

typedef struct EdgeNode {
    int dest;
    int weight; // The weight is of type int
    struct EdgeNode *next;
} EdgeNode;

typedef struct GraphAdjList {
    int vertexNum;
    int edgeNum;
    int isWeighted; // 0 for unweighted graph, 1 for weighted graph
    EdgeNode **adjLists;
} GraphAdjList;

// Create a graph with n vertices
GraphAdjList *createGraphAdjList(int n, int isWeighted);
// Destroy a graph
void destroyGraphAdjList(GraphAdjList *graph);
// Add an edge to the graph
void addEdgeAdjList(GraphAdjList *graph, int u, int v, int w);
// Remove an edge from the graph
void removeEdgeAdjList(GraphAdjList *graph, int u, int v);
// Print the graph
void printGraphAdjList(GraphAdjList *graph);

#endif //ADJACENCYLIST_H

AdjacencyList.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include "AdjacencyList.h"
#include <stdio.h>
#include <stdlib.h>

// Create a graph with n vertices and m edges
GraphAdjList *createGraphAdjList(int n, int isWeighted) {
    GraphAdjList *graph = (GraphAdjList *) malloc(sizeof(GraphAdjList));
    graph->vertexNum = n;
    graph->edgeNum = 0;
    graph->isWeighted = isWeighted;
    graph->adjLists = (EdgeNode **) malloc(sizeof(EdgeNode *) * (n + 1));
    for (int i = 0; i <= n; ++i)
        graph->adjLists[i] = NULL;
    return graph;
}

// Destroy a graph
void destroyGraphAdjList(GraphAdjList *graph) {
    for (int i = 1; i <= graph->vertexNum; ++i) {
        EdgeNode *p = graph->adjLists[i];
        while (p != NULL) {
            EdgeNode *q = p;
            p = p->next;
            free(q);
        }
    }
    free(graph->adjLists);
    free(graph);
}

// Add an edge to the graph
void addEdgeAdjList(GraphAdjList *graph, int u, int v, int w) {
    EdgeNode *p = (EdgeNode *) malloc(sizeof(EdgeNode));
    p->dest = v;
    p->weight = graph->isWeighted ? w : 1;
    p->next = graph->adjLists[u];
    graph->adjLists[u] = p;
    ++graph->edgeNum;
}

// Remove an edge from the graph
void removeEdgeAdjList(GraphAdjList *graph, int u, int v) {
    EdgeNode *p = graph->adjLists[u];
    if (p == NULL) return;
    if (p->dest == v) {
        graph->adjLists[u] = p->next;
        free(p);
        --graph->edgeNum;
        return;
    }
    while (p->next != NULL) {
        if (p->next->dest == v) {
            EdgeNode *q = p->next;
            p->next = q->next;
            free(q);
            --graph->edgeNum;
            return;
        }
        p = p->next;
    }
}

// Print the graph
void printGraphAdjList(GraphAdjList *graph){
    printf("Vertex number: %d\n", graph->vertexNum);
    printf("Edge number: %d\n", graph->edgeNum);
    printf("Weighted: %s\n", graph->isWeighted ? "Yes" : "No");
    for (int i = 1; i <= graph->vertexNum; ++i) {
        printf("%d: ", i);
        EdgeNode *p = graph->adjLists[i];
        if(p == NULL) putchar('^');
        while (p != NULL) {
            printf("%d", p->dest);
            if (graph->isWeighted)
                printf("(%d)", p->weight);
            printf(" ");
            p = p->next;
        }
        printf("\n");
    }
}

test.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//
// This code is used to test functionality.
//

#include <stdio.h>
#include "AdjacencyList.h"

int main() {
    int n, m;
    scanf("%d%d", &n, &m); // 输入图的顶点数和弧(有向边)数
    GraphAdjList *graph = createGraphAdjList(n, 1); // 初始化为n个顶点的带权图
    for(int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdgeAdjList(graph, u, v, w); // 添加一条弧
    }
    printGraphAdjList(graph); // 输出邻接表
    destroyGraphAdjList(graph); // 销毁邻接表
    return 0;
}

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<path>\ADT_AdjacencyList.exe
6 7
1 2 7
1 3 1
1 4 2
2 4 2
3 6 4
4 5 8
5 6 2
Vertex number: 6
Edge number: 7
Weighted: Yes
1: 4(2) 3(1) 2(7)
2: 4(2)
3: 6(4)
4: 5(8)
5: 6(2)
6: ^

进程已结束，退出代码为 0