图的存储与遍历

本节导读

图是数据结构里最「多对多」的结构。大纲在这一章列了图的基本概念、存储及基本操作（邻接矩阵、邻接表、邻接多重表、十字链表）、遍历（深度优先、广度优先）和基本应用，应用放在下一节。

这一节的计算题集中在度与边数的关系、连通所需的边数、存储结构的空间、遍历序列。学完你应该能根据给定的邻接矩阵或邻接表，一步步写出两种遍历序列，并写出用广度优先搜索求单源最短路径的代码。

图的基本概念

图 G 由顶点集 V 和边集 E 组成，顶点数记 n、边数记 e。无向图的边写成 $(v_i, v_j)$(vi​,vj​)，有向图的弧写成 $\langle v_i, v_j \rangle$⟨vi​,vj​⟩（从 $v_i$vi​ 指向 $v_j$vj​）。数据结构里讨论的一般是简单图：没有重复边，也没有顶点到自身的边。

• 度：无向图中顶点的度是与它相连的边数，所有顶点的度之和等于 2e；有向图分入度和出度，入度之和 = 出度之和 = e。
• 路径长度按路径上的边数算；第一个顶点与最后一个相同的路径叫回路；顶点不重复的路径叫简单路径。
• 连通：无向图中两顶点之间有路径就是连通的，任意两顶点都连通的叫连通图，极大连通子图叫连通分量；有向图中任意两顶点双向都有路径叫强连通图，极大强连通子图叫强连通分量。
• 生成树：连通图包含全部 n 个顶点的极小连通子图，有 n − 1 条边；非连通图的各连通分量的生成树组成生成森林。

结论	数值
无向完全图的边数	$\dfrac{n(n-1)}{2}$2n(n−1)​
有向完全图的弧数	$n(n-1)$n(n−1)
n 个顶点的无向连通图	至少 n − 1 条边；多于 n − 1 条必有回路
n 个顶点的强连通有向图	至少 n 条弧（构成一个环）
保证 n 个顶点的无向图在任何情况下都连通	至少 $\mathrm{C}_{n-1}^{2} + 1$Cn−12​+1 条边

最后一条的道理：n − 1 个顶点构成完全图、剩下一个顶点孤立时，边数是 $\mathrm{C}_{n-1}^{2}$Cn−12​，图仍不连通；再多一条边就一定连通。

邻接矩阵与邻接表

邻接矩阵用 n 阶方阵 A 表示：有边（弧）$\langle v_i, v_j \rangle$⟨vi​,vj​⟩ 时 $A[i][j] = 1$A[i][j]=1（带权图存权值），否则为 0（带权图存 ∞，对角线存 0）。邻接表为每个顶点建一个边表（单链表），链着它的所有邻接点；顶点表用数组存放各边表的头指针。

比较项	邻接矩阵	邻接表
空间	$O(n^2)$O(n2)，适合稠密图	$O(n + e)$O(n+e)，适合稀疏图
无向图	矩阵对称，可只存上（下）三角	每条边出现两次，边表结点共 2e 个
有向图的度	第 i 行非零元素个数是出度，第 i 列是入度	边表长度是出度；求入度要扫描全部边表（或另建逆邻接表）
判断两顶点是否相邻	$O(1)$O(1)	要扫描一条边表
表示是否唯一	顶点编号定了就唯一	边表中结点的次序可以不同，不唯一

邻接矩阵还有一个性质：$A^k$Ak 的元素 $A^k[i][j]$Ak[i][j] 等于从 $v_i$vi​ 到 $v_j$vj​ 长度为 k 的路径条数。

十字链表与邻接多重表

十字链表只用于有向图：每条弧一个结点，含弧尾、弧头两个顶点编号和两个链域（同弧头的下一条弧、同弧尾的下一条弧）；每个顶点有两个头指针，分别指向以它为弧头、以它为弧尾的第一条弧。这样出弧和入弧各自成链，求出度、入度都方便。

邻接多重表只用于无向图：每条边只用一个结点，含两个顶点编号和两个链域（分别链向依附于这两个顶点的下一条边）。删除一条边只要改一个结点的链，不像邻接表那样同一条边存两份。

图的遍历

深度优先搜索（DFS）

从某个顶点出发，访问它，再从它的一个未访问的邻接点出发继续深入；走到没有未访问邻接点的顶点就回退，直到所有能到达的顶点都访问过。DFS 是递归的（或用栈），类似树的先序遍历。

广度优先搜索（BFS）

从某个顶点出发，先访问它的全部未访问邻接点，再依次从这些邻接点出发访问它们的邻接点，一层一层向外扩展。BFS 用队列，类似树的层次遍历。对无权图，BFS 按到起点的边数从小到大访问顶点，所以能求单源最短路径（路径长度按边数）。

遍历	辅助结构	邻接矩阵存储	邻接表存储	空间
DFS	栈（递归）	$O(n^2)$O(n2)	$O(n + e)$O(n+e)	$O(n)$O(n)
BFS	队列	$O(n^2)$O(n2)	$O(n + e)$O(n+e)	$O(n)$O(n)

非连通图要在主程序里对每个未访问的顶点调用一次 DFS 或 BFS，调用的次数就是连通分量的个数。遍历时经过的边构成深度优先（广度优先）生成树或生成森林。同一个图用邻接表存储时，边表次序不同，遍历序列和生成树也可能不同。

易错提醒

• ❌ 有 n 个顶点、n − 1 条边的无向图一定连通。✅ n − 1 条边只是连通的必要条件。因为可以一部分顶点构成回路、另一部分顶点孤立。

• ❌ 邻接表存储的无向图有 e 个边表结点。✅ 无向图每条边在两个顶点的边表里各出现一次，共 2e 个。因为边没有方向，两端都要能找到它。

• ❌ 用邻接矩阵存储时，DFS 和 BFS 的时间复杂度是 $O(n + e)$O(n+e)。✅ 是 $O(n^2)$O(n2)。因为找每个顶点的邻接点都要扫描矩阵的一整行。

• ❌ 一个图的深度优先遍历序列是唯一的。✅ 只有存储结构和起点都确定后才唯一。因为邻接点的访问次序取决于边表（或矩阵中列）的次序。

• ❌ 强连通有向图至少要 n − 1 条弧。✅ 至少要 n 条。因为 n − 1 条弧连不成一个能回到起点的环，至少有一个顶点到不了别的顶点或回不来。

例题精讲

例题 1（计算）

无向图有 16 条边，度为 4 的顶点 3 个，度为 3 的顶点 4 个，其余顶点的度都小于 3。这个图至少有多少个顶点？

答题要点示范：度之和 $2e = 32$2e=32；已知的 7 个顶点贡献 $4 \times 3 + 3 \times 4 = 24$4×3+3×4=24，还差 8。其余顶点的度至多为 2，至少还要 4 个顶点。所以至少 3 + 4 + 4 = 11 个顶点。

例题 2（遍历序列）

无向图的邻接表如下（边表按列出的次序链接），写出从顶点 0 出发的 DFS 和 BFS 序列。

顶点	边表中的邻接点（依次）
0	1、2
1	0、3、4
2	0、5
3	1、6
4	1、5
5	2、4、6
6	3、5

答题要点示范：DFS：0 → 1（0 的第一个邻接点）→ 3 → 6 → 5（6 的邻接点 3 已访问）→ 2（5 的第一个未访问邻接点）；2 没有未访问邻接点，回退到 5，访问 4。序列为 0、1、3、6、5、2、4。BFS：0 出队，1、2 入队；1 出队，3、4 入队；2 出队，5 入队；3 出队，6 入队。序列为 0、1、2、3、4、5、6。

点评：DFS 每一步都要回到当前顶点的边表，从头找第一个未访问的邻接点；回退时也一样，别跳到别的顶点。

例题 3（算法设计）

设问：无权图用邻接表存储，设计算法求从顶点 v 到其余各顶点的最短路径长度（边数），不可达的记为 −1。

答题要点示范：思想是从 v 做 BFS，顶点第一次被访问时的层数就是最短路径长度：d[v] = 0，从 u 首次到达邻接点 w 时 d[w] = d[u] + 1。

#define MAXV 100
typedef struct ArcNode {           /* 边表结点 */
    int adjvex;                    /* 邻接点编号 */
    struct ArcNode *nextarc;
} ArcNode;
typedef struct {
    ArcNode *first[MAXV];          /* 各顶点边表的头指针 */
    int n;                         /* 顶点数 */
} ALGraph;
void bfs_dist(ALGraph *G, int v, int d[]) {
    int Q[MAXV], front = 0, rear = 0;
    for (int i = 0; i < G->n; i++) d[i] = -1;   /* -1 表示尚未到达 */
    d[v] = 0;
    Q[rear++] = v;
    while (front != rear) {
        int u = Q[front++];
        for (ArcNode *p = G->first[u]; p != NULL; p = p->nextarc) {
            if (d[p->adjvex] == -1) {
                d[p->adjvex] = d[u] + 1;   /* 第一次到达就是最短 */
                Q[rear++] = p->adjvex;
            }
        }
    }
}

每个顶点入队一次、每条边表结点检查一次，时间复杂度 $O(n + e)$O(n+e)，空间复杂度 $O(n)$O(n)。

点评：d 数组同时起「访问标记」的作用；要在入队时就置好 d，出队时再置会让同一顶点重复入队。

本节小结

• 度之和等于 2e；无向完全图 $\dfrac{n(n-1)}{2}$2n(n−1)​ 条边；连通至少 n − 1 条边，强连通至少 n 条弧，保证连通要 $\mathrm{C}_{n-1}^{2} + 1$Cn−12​+1 条边。
• 邻接矩阵 $O(n^2)$O(n2) 空间，适合稠密图；邻接表 $O(n + e)$O(n+e)，适合稀疏图，无向图边表结点 2e 个。
• 十字链表用于有向图，出入度都好求；邻接多重表用于无向图，每条边一个结点。
• DFS 用栈、BFS 用队列；邻接矩阵 $O(n^2)$O(n2)、邻接表 $O(n + e)$O(n+e)；BFS 能求无权图单源最短路径；遍历调用次数等于连通分量数。