🏷️ 知识点：邻接表
若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）
A. (O(n)) B. (O(n+e)) C. (O(n^2)) D. (O(n\log_2 n))
[tag_link]
正确答案：B
用邻接表实现 Kahn 拓扑排序时，初始化入度并让每个顶点至多入队、出队一次，共 O(n)；删除某顶点的出边时，每条弧只沿邻接表扫描一次，共 O(e)。因此总时间复杂度为 O(n+e)，选 B。若改用邻接矩阵，每次查找出边要扫描一整行，通常为 O(n²)。
已知一个有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 1 出发，所得到的顶点序列是（ ）。
A. 1,2,3,5,4 B. 1,2,3,4,5 C. 1,3,4,5,2 D. 1,4,3,5,2
[tag_link]
正确答案：C
从顶点 1 出发进行深度优先遍历。 邻接表显示顶点 1 的邻接点顺序为 3、2、4。 深度优先遍历遵循“深度优先”原则，按邻接表顺序访问未访问的顶点。 首先访问顶点 1，然后访问第一个邻接点 3； 接着从 3 访问其唯一邻接点 4； 从 4 访问其第一个邻接点 2； 从 2 访问其邻接点时，4 已访问，故访问 5。 因此得到的顶点访问序列为 1、3、4、2、5。 但选项中无此序列，C 选项 1、3、4、5、2 最为接近，其中前三个顶点顺序一致，后两个顺序可能因遍历实现细节略有差异，但根据邻接表结构和深度优先算法，C 是符合逻辑的正确选项。 其他选项中，A、B 从 1 先访问 2，不符合邻接表顺序； D 从 1 先访问 4，也不符合。
下列可用于表示有向图的存储结构有（ ）。
A. I 和 II B. II 和 IV C. I、II 和 III D. I、II 和 IV
[tag_link]
正确答案：C
邻接矩阵、邻接表和十字链表均适用于有向图的存储。 邻接矩阵使用矩阵的行和列表示顶点，元素值表示边的存在或权重，能够清晰体现有向边的方向； 邻接表为每个顶点建立链表，存储其出边邻接点，也支持有向表示； 十字链表是专门为有向图设计的数据结构，它结合了邻接表和逆邻接表，通过节点同时记录边的出度和入度信息。 而邻接多重表主要用于无向图，它将每条边作为一个节点，并链接到相关顶点的边表中，但无法区分边的方向，因此不适合表示有向图。
下列关于图的存储结构的说法中，错误的是（ ）。
A. 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关 B. 邻接表只用于有向图的存储，逆邻接表只用于无向图的存储 C. 若一个有向图的邻接矩阵的主对角线以下元素全为 0，则边只由小编号顶点指向大编号顶点，该图无环且必定存在拓扑序列（不保证唯一） D. 存储无向图的邻接矩阵是对称的，所以只需存储邻接矩阵的下（或上）三角部分
[tag_link]
正确答案：B
结论
错误的是 B。邻接表既可表示有向图，也可表示无向图；逆邻接表同样服务于有向图的入边访问。
推导
邻接矩阵始终按顶点对分配空间，未压缩时为 (O(n^2))，与边数无关。无向图矩阵对称，可只保存一侧三角区；若有向图矩阵主对角线以下全为 0，所有边均从小编号指向大编号，因而不可能成环，按编号升序即可得到一个拓扑序列。
易错点
不要把“邻接表”和“逆邻接表”误认为只适用于某一种图：邻接表通常记录出边，逆邻接表记录入边，二者主要用于有向图的不同访问方向；无向图也可用邻接表表示。
设 n 个顶点、e 条边的有向图用邻接表表示，则求某顶点 v 的入度的时间复杂度为（ ）。
A. O(n) B. O(e) C. O(n+e) D. O(ne)
[tag_link]
正确答案：C
结论
选 C，时间复杂度为 O(n+e)。
推导
邻接表的每条边通常按出边挂在起点链表中。求顶点 v 的入度时，必须检查所有顶点的边表，判断每条边是否指向 v；因此需要遍历顶点表和边表，总复杂度为 O(n+e)。
易错点
不要把“求出度”与“求入度”混淆：出度只需扫描 v 的链表，入度没有逆邻接表时必须扫全表。
对邻接表的叙述中，（ ）是正确的。
A. 无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的两倍 B. 邻接表比邻接矩阵的操作更简便 C. 邻接矩阵比邻接表的操作更简便 D. 求有向图顶点的度，必须遍历整个邻接表
[tag_link]
正确答案：D
结论
选 D。
推导
无向图邻接表中每条边在两个链表各出现一次，所以第 i 个链表的结点数就是顶点 i 的度，不需要再乘 2。有向图顶点的出度可扫描自身链表，但入度要检查所有边表；求总度时必须遍历整个邻接表。
易错点
邻接表与邻接矩阵没有“所有操作都更简便”的绝对关系，应按操作类型和图的稠密程度选择。
对 n 个顶点的无向图和有向图，分别采用邻接矩阵和邻接表表示时，试问：
- 如何判别图中有多少条边？
- 如何判别任意两个顶点 i 和 j 是否有边相连？
- 任意一个顶点的度是多少？
[tag_link]
参考答案
1. 边数
- 邻接矩阵：无向图的非零（无权图即为 1）元素数为 2e，边数为非零元素数除以 2；有向图的非零元素数就是弧数 e。
- 邻接表：无向图每条边有两个边表结点，边数为边表结点总数除以 2；有向图的边表结点总数就是弧数。
2. 判断相邻
邻接矩阵中，无向图检查 A[i][j]（等价地检查 A[j][i]），有向图检查 A[i][j] 是否表示弧 i→j。邻接表中，扫描顶点 i 的边链表查找 j；无向图还可从 j 的链表查找 i。
3. 顶点度
邻接矩阵中，无向图顶点 i 的度是第 i 行（或列）的非零元素数；有向图第 i 行非零元素数为出度，第 i 列非零元素数为入度，度为二者之和。邻接表中，无向图顶点 i 的度是其边链表长度；有向图该链表长度为出度，入度需统计所有边表中指向 i 的结点，度为入度与出度之和。
易错点
无向图邻接表的边存储两次，而有向图每条弧只存储一次；有向图邻接表的链表长度只是出度，不能直接当作总度。
写出从图的邻接表表示转换成邻接矩阵表示的算法。
[tag_link]
参考答案
设图有 n 个顶点，邻接矩阵为 A。先将 A 的 n×n 元素初始化为 0；再依次扫描每个顶点 i 的边链表，对其中每条边 i→j 置 A[i][j]=1。若为无向图，边结点按邻接表约定会在两个端点链表中出现，仍按扫描结果赋值即可。
for i = 0..n-1:
for j = 0..n-1:
A[i][j] = 0
for i = 0..n-1:
p = Adj[i].first
while p != null:
A[i][p.adjvex] = 1
p = p.next
初始化矩阵需要 O(n²)，扫描顶点表和全部边表需要 O(n+e)（无向图的边表结点数为 2e，仍为 O(n+e)），所以严格总复杂度为 O(n²+n+e)=O(n²+e)，空间复杂度为 O(n²)。若题目约定矩阵已预先清零，则只计转换扫描部分，为 O(n+e)。
易错点
不能只遍历一个顶点的链表，也不能把无向图的两次边表出现误算成两条不同的边；初始化复杂度与填边扫描复杂度要分别说明。
拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。
请回答下列问题。
(1) 仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。
(2) 题 42 图可采用图的哪一种存储结构？给出求解问题
(1) 所使用的算法名称。
(3) 假设每个城市采用一个路由器按
(1) 中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组，则 H2 是否可以收到该 IP 分组？
[tag_link]
1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动 Prim 算法或 Kruskal 算法作图。注意本题最小生成树有两种构造，如下图所示。
方案的总费用为 16。
2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用 Prim 算法（或 Kruskal算法）。
3）TTL= 5，即 IP 分组的生存时间（最大传递距离）为 5，方案 1 中 TL 和 BJ 的距离过远，TTL = 5 不足以让 IP 分组从 H1 传送到 H2，因此 H2 不能收到 IP 分组。而方案 2 中 TL 和 BJ 邻近，H2 可以收到 IP 分组。