Lecture 21：图的存储及其操作

本讲解决两个问题：图怎样存入内存，以及不同存储结构下基本操作的代价。做题时先看图是稠密还是稀疏、是有向还是无向、是否频繁删边或查入边，再选择存储方式。

21.1 邻接矩阵法

21.1.1 邻接矩阵

定义：#邻接矩阵

描述：设图 $G=(V,E)$ 有 $n$ 个顶点，依次编号为 $v_1,v_2,\cdots,v_n$。用一个 $n\times n$ 的二维数组 $A$ 记录任意两个顶点间是否有边，则 $A$ 称为图 $G$ 的邻接矩阵。

对于不带权图：

$$ A[i][j]= \begin{cases} 1,&\text{若 }(v_i,v_j)\text{ 或 }\langle v_i,v_j\rangle\in E(G)\ 0,&\text{若 }(v_i,v_j)\text{ 或 }\langle v_i,v_j\rangle\notin E(G) \end{cases} $$

• 无向图的边 $(v_i,v_j)$ 没有方向，因此 $A[i][j]=A[j][i]$。
• 有向图的弧 $\langle v_i,v_j\rangle$ 有方向；矩阵第 $i$ 行第 $j$ 列表示从 $v_i$ 指向 $v_j$。
• 简单图通常令 $A[i][i]=0$，即主对角线元素为 $0$。
• 上述数学编号从 $1$ 开始；下文 C 数组的实际下标从 $0$ 开始，应将顶点编号统一映射到 0 至 vexnum-1，不能把公式中的 $v_n$ 直接访问为 Edge[n][...]。

图中顶点顺序固定为 $A,B,C,D,E,F$。无向图的矩阵关于主对角线对称；有向图的第 $i$ 行记录从 $v_i$ 发出的弧，因此一般不对称。

空间复杂度：#邻接矩阵复杂度

$$ O(\lvert V\rvert^2) $$

• 数组大小只取决于顶点数 $\lvert V\rvert$，与实际边数 $\lvert E\rvert$ 无关。
• 因此邻接矩阵适合稠密图；稀疏图会保存大量 $0$，空间浪费明显。

优缺点：

21.1.2 有向图、无向图与度

无向图：#无向图邻接矩阵

在无自环的无向图中，第 $i$ 个顶点的度等于第 $i$ 行（也等于第 $i$ 列）非零元素的个数：

$$ \operatorname{TD}(v_i)=\sum_{j=1}^{n} A[i][j] $$

有向图：#有向图邻接矩阵

对有向图：

$$ \operatorname{OD}(v_i)=\sum_{j=1}^{n} A[i][j] $$

$$ \operatorname{ID}(v_i)=\sum_{j=1}^{n} A[j][i] $$

$$ \operatorname{TD}(v_i)=\operatorname{OD}(v_i)+\operatorname{ID}(v_i) $$

• 第 $i$ 行非零元素个数是 $v_i$ 的出度。
• 第 $i$ 列非零元素个数是 $v_i$ 的入度。
• 求度、入度或出度都要扫描一行或一列，时间复杂度均为：

$$ O(\lvert V\rvert) $$

WARNING · 自环的计数口径 若题目允许自环，无向自环对顶点的度贡献 $2$，不能只把对角线上的一个非零元素计作 $1$；有向自环则对入度、出度各贡献 $1$。408 题目若未特别说明，通常讨论简单图。

带权图：#网的邻接矩阵

描述：带权图（网）的邻接矩阵仍是二维数组，只是将原来的 $1$ 改为边的权值。

在最短路径等算法中通常约定：

$$ A[i][j]= \begin{cases} w_{ij},&\text{若存在从 }v_i\text{ 到 }v_j\text{ 的边，权值为 }w_{ij}\ \infty,&\text{若 }v_i\text{ 到 }v_j\text{ 无边} \end{cases} $$

• 主对角线通常取 $0$，表示顶点到自身的路径长度为 $0$。
• 不能把“不存在的边”也写为 $0$，否则会和权值为 $0$ 的边混淆；因此常使用 $\infty$。
• 若只是存图而不是做最短路径，也可以用专门的 NO_EDGE 标记；具体哨兵值必须与合法权值区分。

21.1.3 邻接矩阵的幂

性质：#邻接矩阵幂

描述：设图 $G$ 的邻接矩阵为 $A$，矩阵元素为 $0/1$，则 $A^k$ 的元素 $A^k[i][j]$ 等于从顶点 $i$ 到顶点 $j$ 的、长度为 $k$ 的游走（walk）数目。

矩阵乘法展开为：

$$ A^2[i][j]=\sum_{r=1}^{n} A[i][r]A[r][j] $$

其中每一个乘积项 $A[i][r]A[r][j]$ 对应一条：

$$ v_i\rightarrow v_r\rightarrow v_j $$

的长度为 $2$ 的游走。

IMPORTANT · 路径与游走 矩阵幂允许中间顶点或边重复，因此严格说统计的是游走，不一定是顶点互异的简单路径。部分教材在这里宽泛地写“路径”，做题时应按矩阵乘法的游走口径理解。

这里还默认无平行边：$0/1$ 矩阵只记录两点是否相邻。若多重图要把不同平行边看作不同的游走，矩阵元素应记录对应顶点间的边数，而不能仍只写 $0/1$。

课件例子：

若顶点为 $A,B,C,D$，则：

$$ A^2[1][4]=a_{1,1}a_{1,4}+a_{1,2}a_{2,4}+a_{1,3}a_{3,4}+a_{1,4}a_{4,4}=1 $$

表示从 $A$ 到 $D$ 恰好有 $1$ 条长度为 $2$ 的游走，即 $A\to B\to D$。本例邻接矩阵为：

21.1.4 代码实现

不带权图结构：

#define MaxVertexNum 100

typedef struct {
    char Vex[MaxVertexNum];
    int Edge[MaxVertexNum][MaxVertexNum];
    int vexnum, arcnum;
} MGraph;

• Vex：顶点表。元素可以是字符，也可以替换为更复杂的顶点信息。
• Edge：邻接矩阵，即边表或弧表。
• vexnum：当前顶点数。
• arcnum：当前边数；有向图中也可理解为当前弧数。

带权图结构：

#define MaxVertexNum 100
#define INFINITY 0x3f3f3f3f

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType Vex[MaxVertexNum];
    EdgeType Edge[MaxVertexNum][MaxVertexNum];
    int vexnum, arcnum;
} MGraph;

易错点：#邻接矩阵易错

• arcnum 是边/弧的数量，不是数组中非零元素数量。无向图的一条边会在矩阵中出现两次。
• 无向图矩阵对称，但有向图不要求对称。
• 带权图中 INFINITY 表示没有边，不能参加普通加法而产生溢出。

---

21.2 邻接表法

21.2.1 图的存储

定义：#邻接表

描述：为图中的每一个顶点建立一个单链表。第 $i$ 个单链表中的结点表示依附于顶点 $v_i$ 的边，这个单链表称为顶点 $v_i$ 的边表；所有顶点表头按顺序存放，整体称为邻接表。

邻接表由两类结点组成：

• 顶点结点构成顺序表，支持按编号直接定位顶点。
• 每个顶点结点之后接一个单链表。
• 边表结点的 adjvex 不保存完整顶点数据，只保存邻接顶点的编号。

firstarc（代码中也常简写为 first）指向该顶点的第一条边/弧；nextarc 将同一顶点的边表结点串成单链表。

21.2.2 无向图的邻接表

存储规则：#无向图邻接表

无向边 $(v_i,v_j)$ 同时与两个顶点相关，因此要写入两份边表结点：

• 在 $v_i$ 的边表中写入 $j$。
• 在 $v_j$ 的边表中写入 $i$。

所以无向图共有：

$$ 2\lvert E\rvert $$

个边表结点，整体空间复杂度为：

$$ O(\lvert V\rvert+2\lvert E\rvert) $$

在渐近意义上也可写为 $O(\lvert V\rvert+\lvert E\rvert)$，但在判断“边表结点数”时必须答 $2\lvert E\rvert$。

求度：

无向图中，顶点 $v_i$ 的边表长度就是其度：

$$ \operatorname{TD}(v_i)=\text{第 }i\text{ 条边表的结点个数} $$

21.2.3 有向图的邻接表

存储规则：#有向图邻接表

对于有向弧：

$$ \langle v_i,v_j\rangle $$

只在弧尾 $v_i$ 的边表中写入 $j$。因此有向图共有：

$$ \lvert E\rvert $$

个边表结点，空间复杂度为：

$$ O(\lvert V\rvert+\lvert E\rvert) $$

度的获取：

• 顶点 $v_i$ 的边表长度就是其出度。
• 若只使用普通邻接表，入边分散在其他顶点的边表中；求 $v_i$ 的入度需要访问全部顶点表头并遍历所有边表。
• 因而求某个顶点入度的时间复杂度为：

$$ O(\lvert V\rvert+\lvert E\rvert) $$

若另外建立逆邻接表，每条弧改为挂在弧头顶点之后，则可直接枚举入边、计算入度，但枚举出边会变得不便；十字链表相当于把两种方向的链同时保留下来。

上半部分为无向图：每条无向边在两个端点的表中各出现一次。下半部分为有向图的普通邻接表：每条弧只在弧尾的出边表中出现一次。

21.2.4 特点与适用性

优点：

• 对稀疏图节省空间，空间随实际边数增长。
• 枚举一个顶点的出边或无向邻接边时，只需遍历该顶点的边表。
• 采用头插法时，若已知顶点下标且无需先判断重边，插入一条边表结点可在 $O(1)$ 时间完成。

缺陷：#邻接表缺陷

• 无向图的一条边保存两份冗余信息。
• 普通有向邻接表只直接保存出边，查询入边和删除顶点时通常需要扫描所有边表。
• 同一图的邻接表不唯一：边表中各邻接点的排列顺序可以不同。
• 上述 $2\lvert E\rvert$ 结点结论默认无向图按常规方式存储且不单独讨论自环；若允许自环，必须按具体实现确定自环建立一个还是两个边表结点，并保证度数按 $2$ 计。

21.2.5 代码实现

#define MaxVertexNum 100
typedef char VertexType;

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
    // InfoType info;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode *first;
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

字段说明：

易错点：#邻接表易错

• 无向图中 arcnum 仍记真实边数 $\lvert E\rvert$，不是边表结点数 $2\lvert E\rvert$。
• 边表的先后顺序不唯一，所以由邻接表得到的 DFS/BFS 遍历序列也可能不同。
• 课件中成员名写作 first；教材中常写作 firstarc，含义相同。

---

21.3 十字链表与邻接多重表

21.3.1 十字链表

定义：#十字链表

描述：十字链表是有向图的一种链式存储方式。一条弧同时被串入弧尾顶点的出弧链和弧头顶点的入弧链，因而能方便地访问出边和入边。

顶点结点：

• 顶点结点之间采用顺序存储。
• firstin 方便找入边，firstout 方便找出边。

弧结点：

对于弧：

$$ \langle v_i,v_j\rangle $$

• tailvex=i，headvex=j。
• 它通过 tlink 接到 $v_i$ 的出弧链。
• 它通过 hlink 接到 $v_j$ 的入弧链。

空间复杂度：

$$ O(\lvert V\rvert+\lvert E\rvert) $$

读图时从顶点结点的 firstout 沿 tlink 走，可枚举同一弧尾的全部出弧；从 firstin 沿 hlink 走，可枚举同一弧头的全部入弧。一条弧结点同时出现在这两条逻辑链中，但物理上只存一份。

优势：

• 有向图中查询一个顶点的入弧和出弧都很方便。
• 删除一条弧或删除一个顶点时，可以沿入弧链、出弧链处理相关弧，比普通邻接表更直接。
• 每条弧只存一个弧结点，没有普通有向邻接表查询入边时的全表扫描问题。
• 经典十字链表的 hlink、tlink 通常仍是单向后继指针；若只给出两个端点而没有目标弧指针，删除前仍需在相应链中查找目标及其前驱，不能无条件宣称删除为 $O(1)$。

21.3.2 邻接多重表

定义：#邻接多重表

描述：邻接多重表是无向图的一种链式存储方式。每条无向边只建立一个边结点，但该结点同时链接到其两个端点的边链表中。

一个边结点通常包含：

顶点结点通常保存：

空间复杂度：

$$ O(\lvert V\rvert+\lvert E\rvert) $$

优势与限制：

• 每条无向边只保存一次，不再像普通无向邻接表那样保存两份边表结点。
• 删除边、删除顶点等操作方便，因为一条边结点知道自己的两个端点及两条后继链接。
• 邻接多重表只适用于无向图。
• 与十字链表类似，“方便删除”不等于任何情况下都是 $O(1)$；若没有已知边结点或前驱信息，仍要先沿关联边链定位。

遍历顶点 $i$ 的关联边时，每到一个边结点都要先判断 $i$ 等于 ivex 还是 jvex：前者沿 ilink，后者沿 jlink。同一边结点由两个端点共享。

21.3.3 四种存储结构对比

选择口诀：

稠密图查边选矩阵；稀疏图遍历邻边选邻接表；有向图还要频繁查入边选十字链表；无向图还要频繁删边删点选邻接多重表。

---

21.4 图的基本操作

21.4.1 基本操作接口

易错点：#图基本操作

• AddEdge 是添加边；原课件文字“向图中删除该边”为笔误，应按函数名和上下文理解为“添加该边”。
• 对有向图，Adjacent(G,x,y) 判断的是 $x\to y$，不能把 $y\to x$ 当作同一条弧。
• 删除顶点不只是删除顶点表项，还必须删除所有与该顶点关联的边或弧。

21.4.2 判断邻接：Adjacent(G, x, y)

邻接矩阵：

直接检查矩阵元素：

$$ A[x][y] $$

故无论有向图还是无向图，时间复杂度均为：

$$ O(1) $$

邻接表：

在顶点 $x$ 的边表中顺序查找 $y$。有向图检查的是 $x$ 的出边表，复杂度为 $O(\operatorname{OD}(x))$；无向图为 $O(\deg(x))$。最坏情况下课件统一记为：

$$ O(\lvert V\rvert) $$

在简单图中，度或出度最多为 $\lvert V\rvert-1$，所以最坏为 $O(\lvert V\rvert)$。

21.4.3 列出邻接边：Neighbors(G, x)

21.4.4 插入顶点：InsertVertex(G, x)

邻接矩阵：

• 若最大容量已经预留，且整张矩阵在建图时已经统一初始化为“无边”，插入孤立顶点只需写顶点表并增加 vexnum，课件记为 $O(1)$。
• 若新增的行、列尚未初始化，则需要写入 $2\lvert V\rvert+1$ 个无边标记，时间为 $O(\lvert V\rvert)$。
• 若容量不足而重新分配并复制整个矩阵，代价可达 $O(\lvert V\rvert^2)$。

邻接表：

• 新增一个顶点表头，将 first 置空即可。
• 时间复杂度：

$$ O(1) $$

新顶点 $X$ 暂时没有关联边，所以对应的新行和新列都为 $0$；带权图则应填入约定的无边标记，并将对角线按题意设为 $0$。

21.4.5 删除顶点：DeleteVertex(G, x)

21.4.6 添加边：AddEdge(G, x, y)

描述：若无向边 $(x,y)$ 或有向弧 $\langle x,y\rangle$ 不存在，则加入该边。

• 邻接矩阵：令 $A[x][y]$ 为 $1$ 或相应权值；无向图还要同步令 $A[y][x]$ 为相同值。
• 邻接表：有向图在 $x$ 的边表插入一个指向 $y$ 的结点；无向图需在 $x$、$y$ 两条边表各插入一个结点。
• 复杂度口径：邻接矩阵判重并写入都是 $O(1)$；邻接表在“题目已保证边不存在”或“允许平行边”且采用头插法时为 $O(1)$。若接口必须先确认边不存在，则普通邻接表还要先查找，代价为 $O(\operatorname{OD}(x))$ 或 $O(\deg(x))$，最坏 $O(\lvert V\rvert)$。

21.4.7 删除边与权值操作

删除边：RemoveEdge(G, x, y)

• 邻接矩阵中将对应位置改为 $0$ 或 $\infty$；无向图同时修改两个对称位置，时间为 $O(1)$。
• 有向邻接表在 $x$ 的出边表中查找并摘除 $y$，时间为 $O(\operatorname{OD}(x))$。
• 无向邻接表需分别从 $x$、$y$ 的边表摘除对称结点，时间为 $O(\deg(x)+\deg(y))$。
• 十字链表、邻接多重表能从两类关联链处理同一弧/边；若已持有目标结点及所需前驱，修改链接可为 $O(1)$，否则仍要计入定位目标和前驱的时间。

边权值：

• Get_edge_value(G,x,y)：读取边 $(x,y)$ 或弧 $\langle x,y\rangle$ 的权值。
• Set_edge_value(G,x,y,v)：将对应边权改为 $v$。
• 邻接矩阵可直接读写 $A[x][y]$，为 $O(1)$；普通邻接表须先在 $x$ 的边表中找到目标边，代价与 Adjacent 相同。

21.4.8 邻接点迭代：FirstNeighbor 与 NextNeighbor

“第一个”和“下一个”由邻接矩阵的列序或邻接表的链内次序决定。邻接表的链内次序不唯一，因此依赖这两个接口的 DFS/BFS 访问序列也可能不唯一。

---

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：图基本概念 · 下一篇：图的遍历
• 关联专题：图代码

21.5 题型与复盘

21.5.1 常见题型

题型一：由图写邻接矩阵或邻接表

• 先给顶点确定编号顺序。
• 无向图矩阵要检查对称性；无向边在邻接表中必须写两次。
• 有向图按弧尾建立边表，不能反向写入。
• 带权图的无边位置按题意填 $\infty$ 或其他约定值。

题型二：由邻接矩阵求度

• 无自环无向图：数任一行的非零元素；若允许自环，主对角线上的自环对度贡献 $2$。
• 有向图：行和为出度，列和为入度，二者和为总度。
• 注意权值不为 $0$ 的带权图依旧按“是否有边”计数，而不是把权值相加。

题型三：邻接矩阵幂的含义

• $A^2[i][j]$：从 $i$ 到 $j$ 的长度为 $2$ 的游走数。
• $A^k[i][j]$：从 $i$ 到 $j$ 的长度为 $k$ 的游走数。
• 游走长度按经过的边数计算，不是经过的顶点数；游走允许重复顶点或边。

题型四：存储结构选择

• 顶点很多、边很少：邻接表。
• 顶点之间关系接近完全图、常判两点是否相邻：邻接矩阵。
• 有向图需同时高效找入边、出边：十字链表。
• 无向图需频繁删除边或顶点：邻接多重表。

21.5.2 本节复盘