13.4.2 图的定义与存储

图由顶点和边构成。有箭头的是有向图，边也称为弧；没有箭头的是无向图。课程中反复提醒：图的存储与图的特性经常结合考，尤其是邻接矩阵是否对称、邻接表节点数量。

基本概念

概念	含义
顶点	图中的节点
边	无向图中两个顶点之间的连接
弧	有向图中带方向的连接
路径	从一个顶点到另一个顶点经过的顶点/边序列
连通图	无向图中任意两个顶点之间都有路径
完全图	任意两个顶点之间都有边或双向弧

注意：有边一定有路径；没有直接边，也可能通过其他顶点形成路径。

完全图

类型	定义	边/弧数量
无向完全图	任意两个顶点之间有一条无向边	$\frac{n(n-1)}{2}$
有向完全图	任意两个顶点之间有两条方向相反的弧	$n(n-1)$

有向图中，A -> B 不等于 B -> A。所以有向完全图每对顶点需要两条弧。

邻接矩阵

邻接矩阵用 $n\times n$ 矩阵表示顶点之间是否有边。若顶点 $v_i$ 到 $v_j$ 有边，则矩阵元素 $A[i][j]$ 记为 1 或权值；没有边则记为 0 或无穷大。

图类型	邻接矩阵特点
无向图	一定对称
有向图	一般不对称
有向完全图且双向权值相同	也可能对称
带权图	矩阵元素可存权值

重要结论：无向图的邻接矩阵一定对称；但邻接矩阵对称不一定说明它是无向图，因为有向图也可能双向都有边。

邻接表

邻接表用一个顶点表保存所有顶点，再为每个顶点挂一条链表，记录它相邻的顶点。

flowchart LR
  V1["v1"] --> V2["v2"]
  V1 --> V4["v4"]
  V1 --> V6["v6"]
  H["顶点表"] --> V1

邻接表中同一顶点后面的相邻顶点顺序通常不唯一，按编号排列只是常见习惯。

空间比较

设顶点数为 $n$，边数为 $e$：

存储方式	空间	特点
邻接矩阵	$O(n^2)$	判断两点是否相邻很快，适合稠密图
邻接表	$O(n+e)$	只存实际边，适合稀疏图

无向图中，一条边在邻接表中通常出现两次；有向图中一条弧出现一次。

本节例题

单选

关于图的存储，下列说法正确的是：

A无向图的邻接矩阵一定对称B对称邻接矩阵一定来自无向图C邻接矩阵适合所有稀疏图D邻接表必须按顶点编号升序存储

自查清单

1. 能否区分边、弧、路径和连通？
2. 能否计算无向完全图和有向完全图的边/弧数量？
3. 能否说出邻接矩阵和邻接表各适合什么图？