考研笔记

图的存储及基本操作

十字链表和邻接多重表是算法竞赛完全不用的两种结构，而 408 明确要考。

算竞存图只有两种写法：邻接矩阵（点少时）和链式前向星 / vector 邻接表。十字链表和邻接多重表这两个名字在竞赛里连出现都不会出现——它们解决的是「无向图删边不方便」「有向图求入度要遍历全表」这类教材场景下的问题。

这一节的落点是表 6.1 那张四列对照表，五行每一行都被单独考过。

机制

邻接矩阵

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）。

或是中的边否则

对带权图， 存权值，不存在的边存 或 。

  • 无向图的邻接矩阵是对称矩阵，可采用压缩存储（只存上三角或下三角）。
  • 空间复杂度 ，与边数无关，适合稠密图。
  • 表示唯一。
  • 无向图中，第 行（或第 列）非零元素的个数正好是顶点 的度；有向图中，第 行非零元素个数是出度，第 列非零元素个数是入度。

邻接表

对图 中每个顶点 建立一个单链表（边表），链表中的结点表示依附于 的边（有向图中是以 为尾的弧）。

教材列出的五条性质，④ 和 ⑤ 是考点：

④ 在无向图的邻接表中，求某个顶点的度只需计算其邻接表中的边表结点个数。在有向图的邻接表中，求某个顶点的出度只需计算其邻接表中的边表结点个数；但求某个顶点 的入度则需遍历全部的邻接表，统计邻接点（adjvex）域为 的边表结点个数。

⑤ 图的邻接表表示并不唯一，因为在每个顶点对应的边表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

  • 空间复杂度：无向图 （每条边存两次）；有向图 。
  • 适合稀疏图。

边界辨析：

「求有向图的入度必须遍历整个邻接表」是十字链表存在的全部理由。 表 6.1 里邻接表那一列的「找相邻边」格子写的就是这句话。 记住这条因果，十字链表的两个链域（hlink/tlink）就不用死记了。

十字链表（只能存有向图）

十字链表是有向图的一种链式存储结构。 有向图的**每条弧用一个结点（弧结点）**来表示，**每个顶点也用一个结点（顶点结点）**来表示。

弧结点中有 5 个域：

tailvexheadvexhlinktlink(info)
  • tailvex 域和 headvex 域分别存放弧尾和弧头这两个顶点的编号；
  • 头链域 hlink 指向弧头相同的下一条弧；
  • 尾链域 tlink 指向弧尾相同的下一条弧；
  • info 域存放该弧的相关信息。

这样，弧头相同的弧在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有 3 个域：

datafirstinfirstout
  • data 存放该顶点的数据信息；
  • firstin 指向以该顶点为弧头的第一条弧；
  • firstout 指向以该顶点为弧尾的第一条弧。

在十字链表中，既容易找到 为尾的弧，也容易找到 为头的弧，因而容易求得顶点的出度和入度。 图的十字链表表示是不唯一的，但一个十字链表表示唯一确定一个图。

顶点结点之间是顺序存储的。

邻接多重表（只能存无向图）

邻接多重表是无向图的一种链式存储结构。

动机：在邻接表中，容易求得顶点和边的各种信息，但求两个顶点之间是否存在边而执行删除边等操作时，需要分别在两个顶点的边表中遍历，效率较低。

边结点：

ivexilinkjvexjlink(info)
  • ivex 域和 jvex 域存放该边依附的两个顶点的编号；
  • ilink 指向依附于顶点 ivex 的下一条边；
  • jlink 指向依附于顶点 jvex 的下一条边。

顶点结点：

datafirstedge

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，因为每条边依附于两个顶点，所以每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于：同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

关联对照：

十字链表 : 有向图 = 邻接多重表 : 无向图。 两者是同一思想的两个版本： 让一条边（弧）只用一个结点，同时挂进两条链，从而两端都好找、删除也方便。 区别只是有向图的两条链是「弧头链 / 弧尾链」，无向图的两条链是「依附于 的链 / 依附于 的链」。 记住这一句，四个域名（hlink/tlink 与 ilink/jlink）就不会互串。

表 6.1 图的四种存储方式的总结

邻接矩阵邻接表十字链表邻接多重表
空间复杂度无向图 ；有向图
找相邻边遍历对应行或列的时间复杂度为 找有向图的入度必须遍历整个邻接表很方便很方便
删除边或顶点删除边很方便，删除顶点需要大量移动数据无向图中删除边或顶点都不方便很方便很方便
适用于稠密图稀疏图和其他只能存有向图只能存无向图
表示方式唯一不唯一不唯一不唯一

这张表是本节的全部产出，五行都要能默写。

图的基本操作

图的基本操作是独立于图的存储结构的。 而对于不同的存储方式，操作算法的具体实现会有着不同的性能。

操作含义
Adjacent(G,x,y)判断图 是否存在边 或
Neighbors(G,x)列出图 中与结点 邻接的边
InsertVertex(G,x)在图 中插入顶点
DeleteVertex(G,x)从图 中删除顶点
AddEdge(G,x,y)若边不存在，则向图 中添加该边
RemoveEdge(G,x,y)若边存在，则从图 中删除该边
FirstNeighbor(G,x)求 的第一个邻接点，若有则返回顶点号；若 没有邻接点或图中不存在 ，则返回
NextNeighbor(G,x,y)假设 是 的一个邻接点，返回除 外 的下一个邻接点的顶点号；若 是 的最后一个邻接点，则返回

FirstNeighbor / NextNeighbor 这对操作是 6.3 遍历算法 的接口——教材的 BFS/DFS 伪代码全部写在这两个函数之上，从而与具体存储结构解耦。

手算模板

选存储结构：

条件选择
稠密图 / 要 判断两点是否相邻邻接矩阵
稀疏图 / 要遍历邻接点邻接表
有向图且要频繁求入度十字链表
无向图且要频繁删边邻接多重表

由邻接矩阵求度：无向看行（或列）；有向行是出度、列是入度。

判断表示是否唯一：只有邻接矩阵唯一，其余三种都不唯一（取决于边的输入次序）。

边界

说法判断说明
「邻接矩阵的空间与边数有关」❌恒为
「邻接矩阵表示不唯一」❌唯一（顶点编号确定后）
「邻接表表示唯一」❌不唯一，取决于边的输入次序
「有向图邻接表求入度很方便」❌必须遍历整个邻接表
「无向图邻接表的空间是 」❌是 ，每条边存两次
「邻接矩阵删除顶点很方便」❌需要大量移动数据；删边才方便
「十字链表可以存无向图」❌只能存有向图
「邻接多重表可以存有向图」❌只能存无向图
「十字链表表示唯一确定一个图」✅反过来「一个图的十字链表唯一」是错的
「邻接多重表中一条边用两个结点」❌只有一个结点；邻接表才是两个
「hlink 指向弧尾相同的下一条弧」❌hlink 是头链（弧头相同），tlink 是尾链
「firstin 指向以该顶点为弧尾的第一条弧」❌firstin 是弧头，firstout 是弧尾
「图的基本操作依赖存储结构」❌操作独立于存储结构，只是实现性能不同
「FirstNeighbor 无邻接点时返回 0」❌返回

口径差异：

算竞存图只有两套：邻接矩阵（ 小）和链式前向星 / vector 邻接表。 求入度就在读边时顺手 indeg[v]++，删边基本不做（改成标记）。 所以「求入度不方便」「删边不方便」这两个痛点在算竞里根本不存在—— 也就没有十字链表和邻接多重表的位置。 408 的 2024 年真题直接考了「图的邻接多重表表示的分析」，这一节必须按教材从零学。

对照速查

结构存什么图空间唯一强项
邻接矩阵都可唯一稠密图； 判邻接
邻接表都可无向 / 有向 不唯一稀疏图
十字链表仅有向不唯一出度入度都好求
邻接多重表仅无向不唯一删边方便
结点域十字链表（有向）邻接多重表（无向）
边/弧结点tailvex headvex hlink tlink infoivex ilink jvex jlink info
顶点结点data firstin firstoutdata firstedge

考点

  • 表 6.1 五行——每行都被单独考过。
  • 有向图邻接表求入度要遍历整个表。
  • 邻接表表示不唯一，邻接矩阵唯一。
  • 十字链表只存有向图、邻接多重表只存无向图。
  • 图的邻接多重表表示的分析（2024 命题追踪）。
  • 弧结点/边结点的域名与指向。
  • FirstNeighbor/NextNeighbor 返回 的两种情形。

链接

反向链接