定义图、顶点、边、路径和连通性,比较邻接矩阵、邻接表、十字链表与邻接多重表的表示方法和操作代价。
# 一、图的基本概念
图由顶点集合 和边集合 构成,记作 。边连接顶点;若边有方向,称有向图,否则称无向图。带权图的边还关联一个权值,可表示距离、费用或持续时间。
| 概念 | 含义 |
|---|---|
| 无向边 | 无序顶点对 ,从 到 与从 到 等价 |
| 有向边或弧 | 有序顶点对 ,方向从 指向 |
| 顶点的度 | 无向图中与顶点关联的边数 |
| 入度、出度 | 有向图中以顶点为终点、以顶点为起点的弧数 |
| 路径 | 沿边依次经过的顶点序列,路径长度通常按边数计 |
| 回路 | 起点和终点相同的路径 |
| 连通图 | 无向图中任意两顶点间均有路径 |
| 强连通图 | 有向图中任意两顶点间均可互相到达 |
| 连通分量 | 无向图的极大连通子图 |
| 有向无环图(DAG) | 不含有向回路的有向图 |
简单图不含自环和重边。含 个顶点的简单无向完全图有 条边;若为不含自环的简单有向完全图,则有 条弧。
无向图满足握手定理:
有向图中所有顶点入度之和与出度之和都等于弧数:
# 二、邻接矩阵
若顶点编号为 到 ,邻接矩阵用二维数组 保存边。无向图的矩阵关于主对角线对称;有向图中 表示从顶点 到顶点 是否有弧或该弧权值。
1 |
|
无权图可用 表示无边与有边;带权图不宜简单用 表示无边,因为零权边可能合法。通常令 ,无边处为 INF,其余位置存权值。
邻接矩阵判断两点是否相邻为 ,枚举某顶点的所有邻接点需要 ,空间复杂度为 。它适合稠密图,也便于实现 Floyd 等需要访问任意顶点对的算法。
# 三、邻接表
邻接表为每个顶点维护一条链表或动态数组,保存从该顶点出发的邻接点。稀疏图中仅需保存顶点和边,空间复杂度为 。对无向边 ,通常在 和 的邻接表中各记录一次。
1 | typedef struct ArcNode { |
在有向图中,顶点 的邻接表记录从 出发的弧,因此扫描它可得到出度和后继;求入度通常需扫描所有邻接表,或额外保存逆邻接表。无向图的边结点总数通常为 ,但逻辑边数仍是 。
| 表示方法 | 空间 | 判断任意两点相邻 | 枚举顶点邻居 | 适用场景 |
|---|---|---|---|---|
| 邻接矩阵 | 稠密图,频繁查询任意顶点对 | |||
| 邻接表 | 通常需扫描邻接表 | 稀疏图,频繁遍历邻接边 |
# 四、其他链式存储
- 十字链表用于有向图。弧结点同时链接在弧尾的出边链和弧头的入边链上,便于分别遍历顶点的出边与入边。
- 邻接多重表用于无向图。每条无向边只保存一个边结点,并通过两个链接分别接入两个端点的边链,适合边的插入、删除和遍历。
- 边集数组直接保存 边记录,适合按权值排序的 Kruskal 算法,但枚举单个顶点邻居通常需要扫描所有边。
# 五、考场检查清单
- 邻接矩阵的行和列分别表示起点、终点;有向图不要误把矩阵写成对称。
- 无向图邻接表中一条逻辑边通常占两个边结点;边数仍按逻辑边计。
- 带权图中用 INF 表示无边时,初始化对角线为 。
- 邻接矩阵空间与顶点数平方相关,邻接表空间与顶点和边数之和相关。
- 有向图邻接表自然给出出边;入边需要反向组织或额外遍历。
