邻接表

2026 大纲 五（二）图的存储及基本操作 2. 邻接表（另两种见《邻接矩阵》《十字链表与邻接多重表》）。

为空格子付钱，不如只为边付钱

邻接矩阵的问题在《那一篇》里说过：空间 $O(n^2)$ 与边数完全无关。1000 个顶点、2000 条边的图要开一百万个格子，其中 $99.6\mathrm{\%}$ 存的是"这里没有边"。

邻接表换了个思路：只为真实存在的边花空间。每个顶点挂一条链，链上串着它的邻居，有几个邻居就串几个结点。没有边，就没有结点。

于是它长成两级结构：

• 顶点表：长度为 $n$ 的顺序数组，每一项含顶点数据 data 和一个指针 firstarc。
• 边表：每个顶点的 firstarc 挂出一条单链表，结点含 adjvex（邻居的编号）、nextarc，带权图再加一个 info 存权值。

⚠️ 顶点表必须是数组，不能也换成链表。 换了以后"按编号随机访问某个顶点"就从 $O(1)$ 退化成 $O(n)$，而 DFS/BFS 的外层循环、Dijkstra 每一轮的选点，全都建立在这个随机访问上。所以邻接表是"顺序 + 链式"的混合结构，两截各有各的理由。

先动手看一眼

加载可视化中...

拨的时候盯两件事：一是无向图里同一条边出现了两次（两个端点的链上各一份）；二是换个次序建同一张图，链上结点的排列会变——这一点后面会一路影响到遍历序列。

数结点：无向图是 $2e$ 个，那个 2 不能丢

边结点到底有多少个？分两种情况，而且差一倍：

• 有向图 $e$ 个。弧 $⟨u,v⟩$ 只挂在弧尾 $u$ 的链上。
• 无向图 $2e$ 个。边 $(u,v)$ 必须在 $u$ 和 $v$ 两条链上各存一份。

无向图为什么非得存两份？因为邻接表是"从某个顶点出发去找它的邻居"的结构。只在 $u$ 的链上挂一份，那么从 $v$ 出发遍历时就永远看不到这条边——DFS/BFS 会漏掉整片区域。所以这不是冗余，是这个结构能正常工作的前提。

由此空间是 $O(n+e)$，但里面的 $n$ 和 $e$ 都不能省：

• 省掉 $e$（写成 $O(n)$）是错的，边结点实实在在占着空间。
• 省掉 $n$（写成 $O(e)$）也是错的——即使一条边都没有，顶点表仍然占 $n$ 个单元。这一条在真题里被专门设过陷阱，下面还会再碰到。

出度容易，入度困难

这是邻接表最重要的一处不对称，也是后面两种存储结构存在的全部理由。

有向图求出度：顶点 $i$ 的出度就是第 $i$ 条链的长度，沿链数一遍，$O({\mathrm{deg}}^{+}(i))$。

有向图求入度：麻烦了。指向 $i$ 的那些弧，分散在别的顶点的链上，邻接表里没有任何地方汇总过它们。想知道有几条，只能把全部 $n$ 条链走一遍，逐个看 adjvex 是不是 $i$：

// 有向图求入度：无法只看第 i 条链，必须扫全表
int inDegree(ALGraph *G, int i) {
    int d = 0;
    for (int u = 0; u < G->vexnum; u++)
        for (ArcNode *p = G->vertices[u].first; p; p = p->next)
            if (p->adjvex == i) d++;
    return d;
}

代价是 $O(n+e)$：外层扫 $n$ 个链头，内层总共经过 $e$ 个边结点。

🔴 这里的 $n$ 不能扔。有人会觉得"反正是在数边，写 $O(e)$ 就行"——但即使某个顶点的链是空的，你也得访问一次它的表头才知道它是空的。当图极稀疏、$e<n$ 时，扫表头的 $O(n)$ 才是主要开销。$O(n+e)$ 与 $O(max(n,e))$ 是同一个量，真题出现过写成 $max$ 形式的版本，别因为长得不一样就否掉它。

针对入度这个短板，有两条补救路线：

1. 逆邻接表：另建一套链，串"进入 $v_i$ 的弧"。求入度降到 $O({\mathrm{deg}}^{-})$，代价是求出度反过来变难，而且两张表要同步维护。
2. 十字链表：让一份弧结点同时挂在弧尾链和弧头链上，两个方向都是 $O(\mathrm{deg})$，还省掉了同步。它是逆邻接表的进化版。

建表用头插，代价是次序反了

建表时在链头插结点，$O(1)$；尾插要么走到链尾（$O(\mathrm{deg})$），要么额外维护尾指针。所以标准写法是头插：

typedef struct ArcNode {         // 边结点
    int adjvex;                  // 该边指向的顶点编号
    // int weight;               // 带权图可加权值字段（教材称 info）
    struct ArcNode *next;
} ArcNode;

typedef struct VNode {           // 顶点结点
    char data;
    ArcNode *first;              // 指向第一条边
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;            // 顶点数组（顺序存储，支持按编号随机访问）
    int vexnum, arcnum;
} ALGraph;

// 插入无向边 (u, v)：两端各插一个边结点（头插法）
void addEdge(ALGraph *G, int u, int v) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = v;
    p->next = G->vertices[u].first;   // 头插：新结点先指向原链头
    G->vertices[u].first = p;         // 再让表头指向新结点，顺序不能反

    ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
    q->adjvex = u;
    q->next = G->vertices[v].first;
    G->vertices[v].first = q;

    G->arcnum++;                      // 一条无向边只计一次
}

头插带来的副作用是链上次序与输入次序相反。这看起来是个实现细节，但它引出了邻接表最要紧的一条性质。

表示不唯一，以及它一路传导出去的后果

同一张图，边的输入次序不同、建表算法不同，链上结点的排列就不同。所以：

🔴 邻接表的表示不唯一（而邻接矩阵是唯一的）。

这一条会顺着传导下去，直接决定后面三章的题该怎么答：

• DFS/BFS 的遍历序列不唯一——每个顶点先访问哪个邻居，取决于链上次序。
• DFS/BFS 生成树不唯一——序列都变了，树自然跟着变。
• 拓扑序列不唯一——同时有多个入度为 0 的顶点时，先取哪个也是自由的。

反过来用更常出现：题目问"下列哪个不是该图的 DFS 序列"。潜台词是你可以自由选择每个顶点邻居的检查顺序，只要存在某一种顺序能生成这个序列，它就是合法的；四个选项里只有一个无论怎么选顺序都排不出来。判这类题千万别按"编号从小到大"这一种固定次序去核对，那样会把三个合法选项全判成错的。

带权图的权放在哪

权值加在边结点里（教材称 info 字段），不能放顶点结点。理由很直接：权属于"边"，而一个顶点身上挂着多条边，权值各不相同，顶点结点放不下。

无向图的两个副本各存一份相同的权，所以改权时两份都要改，漏一份就会让这张图从一个方向看和从另一个方向看权值不一致。

各操作代价的来历

操作	时间复杂度	代价的来历
建立邻接表	$O(n+e)$	$n$ 个表头初始化 + 每条边一次 $O(1)$ 头插
判断 $(v_i,v_j)$ 是否为边	$O(\mathrm{deg}(v_i))$，最坏 $O(n)$	沿链顺序查找，链最长可达 $n-1$
求出度（有向）/ 度（无向）	$O(\mathrm{deg}(v_i))$	数一条链的长度
求入度（有向）	$O(n+e)$	遍历全部 $n$ 条链共 $e$ 个边结点
统计边数	$O(n+e)$	扫遍所有边链表，无向图结果要除以 2
插入一条边	$O(1)$	头插
删除一条边	$O(\mathrm{deg}(v_i))$	单链表删除要先找到前驱；无向图两条链上各删一次
DFS / BFS 全图遍历	$O(n+e)$	每个顶点入栈/入队一次贡献 $O(n)$；每个边结点被检查恰好一次贡献 $O(e)$
拓扑排序	$O(n+e)$	每个顶点出队一次、每条边被松弛一次

最后两行都被真题单独问过，而且它们的 $O(n+e)$ 来历完全相同：顶点各处理一次给出 $n$，边各被看一次给出 $e$。凡是"在邻接表上把整张图过一遍"的算法，复杂度都是这个形状。换成邻接矩阵就变成 $O(n^2)$，因为找某个顶点的邻居必须扫完一整行。

四顶点有向图的邻接表与逆邻接表走查（想手画一遍就展开）

有向图：$⟨0,1⟩,⟨0,2⟩,⟨1,2⟩,⟨2,0⟩,⟨3,2⟩$。

邻接表（按弧的输入次序头插，故链上次序与输入相反）：

顶点	边链表（出弧）	链长 = 出度
0	2 → 1 → ∧	2
1	2 → ∧	1
2	0 → ∧	1
3	2 → ∧	1

逆邻接表（链上串入弧的来源）：

顶点	边链表（入弧来源）	链长 = 入度
0	2 → ∧	1
1	0 → ∧	1
2	3 → 1 → 0 → ∧	3
3	∧	0

自检：出度之和 $=5$、入度之和 $=5$，两者都等于弧数 $e=5$ ✓。顶点 3 的入度为 0，拓扑排序会第一个输出它。⚠️ 但这张图排不出完整的拓扑序列——$0\to 2$ 与 $2\to 0$ 构成一个环，输出 3 之后剩下三个顶点入度都降不到 0，算法就停在那里。这正是 count < n 判环的场景。

边结点总数：邻接表 5 个、逆邻接表 5 个，合计 10 个。换成十字链表只要 5 个弧结点就能同时支持两个方向。

由邻接表构造逆邻接表，代价 $O(n+e)$：

void buildReverse(ALGraph *G, ALGraph *R) {
    R->vexnum = G->vexnum;
    R->arcnum = G->arcnum;
    for (int i = 0; i < R->vexnum; i++) R->vertices[i].first = NULL;

    for (int u = 0; u < G->vexnum; u++)
        for (ArcNode *p = G->vertices[u].first; p; p = p->next) {
            // 原图有弧 u → p->adjvex，逆图就在 p->adjvex 的链上挂一个 u
            ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
            q->adjvex = u;
            q->next = R->vertices[p->adjvex].first;
            R->vertices[p->adjvex].first = q;
        }
}

图注：左边是一个 4 顶点无向图，右边是它的邻接表。注意右边一共有 6 个边结点而图上只有 3 条边——每条无向边在两个端点的链上各存了一份。同时留意顶点表这一列是紧挨着的方格 （顺序存储、可随机访问），只有边链表才是指针串起来的。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.7 无向图的邻接表表示，p356

邻接矩阵与邻接表互转，以及两个方向的代价为什么不对称

邻接矩阵 → 邻接表：遍历矩阵第 $i$ 行，若 $A[i][j]=1$ 就在顶点 $i$ 的链上插入结点 $j$。

// 内层 j 从大到小扫：头插会让链上次序反转，倒着扫正好让链上编号升序
void MatToList(int A[][MaxVertexNum], ALGraph *G) {
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].first = NULL;
        for (int j = G->vexnum - 1; j >= 0; j--)
            if (A[i][j] == 1) {
                ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->next = G->vertices[i].first;
                G->vertices[i].first = p;
            }
    }
}

void ListToMat(ALGraph *G, int A[][MaxVertexNum]) {
    for (int i = 0; i < G->vexnum; i++)          // 必须先清零：矩阵要为"无边"负责
        for (int j = 0; j < G->vexnum; j++)
            A[i][j] = 0;
    for (int i = 0; i < G->vexnum; i++)
        for (ArcNode *p = G->vertices[i].first; p; p = p->next)
            A[i][p->adjvex] = 1;
}

方向	时间复杂度	为什么
矩阵 → 表	$O(n^2)$	必须看遍每一格才知道哪里有边，即使图很稀疏
表 → 矩阵	$O(n^2+e)$	清零本身就要 $O(n^2)$，之后填边只要 $O(e)$

只要一端是邻接矩阵，就逃不掉 $O(n^2)$——这与"邻接矩阵的空间与边数无关"是同一件事。

FirstNeighbor 与 NextNeighbor 这对抽象接口（读到用它们描述算法的代码时展开）

• FirstNeighbor(G, v)：返回 $v$ 的第一个邻接点，没有则返回 $-1$。
• NextNeighbor(G, v, w)：返回 $v$ 相对于 $w$ 的下一个邻接点，$w$ 是最后一个则返回 $-1$。

有了它们，遍历"$v$ 的所有邻接点"就能写成与存储结构无关的一行：

for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) { /* 处理 w */ }

这层抽象的价值是让同一份 DFS / BFS / 拓扑排序代码在两种存储结构上都能跑——DFS、BFS、BFS 最短路径里的算法描述用的都是这套接口。

// 邻接表实现：沿链走
int FirstNeighbor(ALGraph *G, int v) {
    ArcNode *p = G->vertices[v].first;
    return p ? p->adjvex : -1;
}
int NextNeighbor(ALGraph *G, int v, int w) {
    for (ArcNode *p = G->vertices[v].first; p; p = p->next)
        if (p->adjvex == w)                        // 先找到 w 这个结点……
            return p->next ? p->next->adjvex : -1; // ……再取它的后继
    return -1;
}

// 邻接矩阵实现：扫行，代价 O(n)
int FirstNeighbor_M(MGraph *G, int v) {
    for (int j = 0; j < G->vexNum; j++)
        if (G->edge[v][j] != 0) return j;
    return -1;
}
int NextNeighbor_M(MGraph *G, int v, int w) {
    for (int j = w + 1; j < G->vexNum; j++)        // 从 w 之后接着扫
        if (G->edge[v][j] != 0) return j;
    return -1;
}

两处值得注意：

1. 返回 $-1$ 而不是 0 表示"没有了"。0 是一个合法的顶点编号，用它当哨兵会把"邻接点是 0 号顶点"误判成"没有邻接点"。循环条件写成 w >= 0 正是与这个约定配套的。
2. 邻接表版的 NextNeighbor 写成上面这样是 $O(\mathrm{deg}(v))$（每次都要重新找到 $w$），整趟遍历因此退化成 $O({\mathrm{deg}}^2)$。实际代码里应当直接持有指针 p 往下走，把整趟压回 $O(\mathrm{deg})$；这套接口只是为了描述算法时不依赖具体存储结构。

考点速记

三条结论，正文里都推过：

1. 两级结构：顶点表顺序、边表链式；空间 $O(n+e)$，无向图边结点 $2e$ 个。
2. 出度沿自己的链 $O(\mathrm{deg})$，入度必须扫全表 $O(n+e)$——逆邻接表与十字链表的动机。
3. 邻接表不唯一，由此 DFS/BFS 序列、生成树、拓扑序列都不唯一。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 求某顶点入度的复杂度：正确答案是 $O(n+e)$，而选项里可能写成 $O(max(|V|,|E|))$——这两个式子是同一个量，别因为形状不同就排除它。同一题的干扰项是 $O(|E|)$：它漏掉了"即使某条链是空的也得访问一次表头"这部分开销，在 $e<n$ 的极稀疏图上不成立。
• 在邻接表上跑遍历/拓扑排序的复杂度：BFS 问过一次、拓扑排序问过一次，答案都是 $O(n+e)$，四个选项通常是 $O(n)$ / $O(e)$ / $O(n+e)$ / $O(n\times e)$。记住来历——顶点各处理一次给 $n$，边各看一次给 $e$。
• 存储选型的判断：把"存储稀疏图，用邻接矩阵比邻接表更省空间"作为错误命题，混在三选项判断题里。
• 作为最短路算法的载体：跨科目的综合题里，把一张带权网络交给你，用邻接表组织后跑 Dijkstra 求最短路径树。

易错：$O(n+e)$ 里的 $n$ 不能省。 写成 $O(e)$ 是错的——顶点表要占 $n$ 个单元，扫全表也要访问 $n$ 个表头，$e=0$ 时这部分开销就是全部开销。

易错：无向图的边结点是 $2e$ 个，不是 $e$ 个。 问"这张邻接表共有多少个边结点"，先看图是有向还是无向。

易错：判"某序列是不是合法的 DFS/BFS 序列"时，邻居的检查顺序可以自由选。 邻接表表示不唯一是这类题成立的前提；按"编号从小到大"一种固定次序去核对，会把合法选项误判成非法。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p156，§6.4.2： 邻接表由"表头结点表"和"边表"两部分组成，表头结点含 data 与 firstarc， 边结点含 adjvex、info、nextarc；同页指出 "在有向图中，第 $i$ 个链表中的结点个数只是顶点 $v_i$ 的出度，为求入度，必须遍历整个邻接表"， 并给出逆邻接表的做法。
• 同书印刷 p158：邻接表优缺点小节——空间复杂度 $O(n+e)$、适合稀疏图； "不便于判断顶点之间是否有边……最坏情况下要耗费 $O(n)$ 时间"； 以及"一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一"。
• 同书印刷 p164（§6.5.2 算法分析）：用邻接矩阵存储时遍历为 $O(n^2)$， 用邻接表存储时为 $O(n+e)$——本篇遍历一行的复杂度以此为准。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.7，p356。

相关知识

邻接矩阵（$O(1)$ 判边、$O(n)$ 求入度，完整对比表在那一篇）｜ 十字链表与邻接多重表（一份边结点挂两条链）｜ BFS / DFS（邻接表上遍历 $O(n+e)$，序列随链上次序而变）｜ 拓扑排序（Kahn 在邻接表上一次遍历完成入度递减）｜ 单链表（边链表就是不带头结点的单链表）

相关文章

• 图的基本概念
• 邻接矩阵
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2026Q62分2016Q72分2014Q4210分2012Q52分2011Q82分