第5章 图 — 基本概念、存储结构、遍历与最小生成树
本讲义系统整理了图论的基础知识、图的两种核心存储结构（邻接矩阵与邻接表）、图的遍历算法（DFS 与 BFS）、最小生成树算法（Kruskal 与 Prim），并附带了详尽的配套练习题、详细解析以及常用图算法的 C++ 代码实现。
5.1 图的基本概念
1. 图的分类
- 无向图 (Undirected Graph)：图中的边是没有方向的。若顶点 $v_i$ 和 $v_j$ 之间有边，则用无序对 $(v_i, v_j)$ 表示。
- 有向图 (Directed Graph)：图中的边是有方向的（通常称为弧）。若从顶点 $v_i$ 到 $v_j$ 有一条有向边，则用有序对 $\langle v_i, v_j \rangle$ 表示，其中 $v_i$ 为起点（弧尾），$v_j$ 为终点（弧头）。
- 完全图 (Complete Graph)：任意两个不同顶点之间都存在边连接的图。
- 完全无向图：任意两个顶点间都有一条无向边。含有 $n$ 个顶点的完全无向图边数为： $$\frac{n(n-1)}{2}$$
- 完全有向图：任意两个顶点间都存在方向相反的两条弧。含有 $n$ 个顶点的完全有向图弧数为： $$n(n-1)$$
- 子图 (Subgraph)：设 $G = (V, E)$ 是一个图，若 $G' = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$，则称 $G'$ 是 $G$ 的一个子图。
- 带权图/网 (Weighted Graph / Network)：边或弧上带有某种数值（称为权，如表示距离、运费等）的图。
2. 边数与顶点的关系
对于一个含有 $n$ 个顶点的图 $G$： * 若 $G$ 是无向图，边数 $e$ 满足： $$0 \le e \le \frac{n(n-1)}{2}$$ * 若 $G$ 是有向图，边数 $e$ 满足： $$0 \le e \le n(n-1)$$
3. 连通性
- 连通图 (Connected Graph)：在无向图中，如果任意两个顶点之间都是连通的（即存在一条路径），则称该图为连通图。
- 强连通图 (Strongly Connected Graph)：在有向图中，若对于任意一对顶点 $v_i$ 和 $v_j$，从 $v_i$ 到 $v_j$ 和从 $v_j$ 到 $v_i$ 都存在路径，则称该图为强连通图。
- 连通分量 (Connected Component)：无向图的极大连通子图。
- 强连通分量 (Strongly Connected Component)：有向图的极大强连通子图。
4. 顶点的度 (Degree)
- 度 (Degree)：与顶点相连的边的数目，记作 $D(v)$。
- 入度与出度（有向图）：
- 出度 (Out-degree)：以顶点 $v$ 为起点的有向边数，记作 $OD(v)$。
- 入度 (In-degree)：以顶点 $v$ 为终点的有向边数，记作 $ID(v)$。
- 有向图中顶点的度为入度与出度之和：$D(v) = ID(v) + OD(v)$。
- 度与边数定理： 任何图中，所有顶点的度数之和等于边（或弧）数的 2 倍： $$\sum_{i=1}^{n} D(v_i) = 2e$$
5. 路径与回路 (Paths and Cycles)
- 路径：顶点 $A$ 到顶点 $B$ 经过的顶点序列及其边。
- 简单路径：路径中除了起点和终点外，其余顶点各不相同的路径。
- 回路（环）：起点和终点相同的路径。
- 简单回路：除起点和终点相同外，其余顶点互不相同的回路。
5.2 图的存储结构
1. 邻接矩阵 (Adjacency Matrix) 表示法
邻接矩阵是使用一个二维数组 A[n][n] 来表示图的结构，其中 $n$ 是顶点个数。
- 无权图的邻接矩阵：
$$A[i][j] = \begin{cases}
1, & \text{若顶点 } v_i \text{ 到 } v_j \text{ 有边/弧} \
0, & \text{否则}
\end{cases}$$
- 无向图的邻接矩阵是对称矩阵。第 $i$ 行（或列）中 $1$ 的个数等于顶点 $v_i$ 的度。
- 有向图的邻接矩阵可能不对称。第 $i$ 行元素之和等于顶点 $v_i$ 的出度；第 $j$ 列元素之和等于顶点 $v_j$ 的入度。
- 带权图的邻接矩阵： $$A[i][j] = \begin{cases} w_{ij}, & \text{若顶点 } v_i \text{ 到 } v_j \text{ 有边/弧，且权值为 } w_{ij} \ 0 \text{ 或 } \infty, & \text{若 } i = j \ \infty, & \text{其他情况（即无边连接）} \end{cases}$$
- 优缺点：
- 优点：结构简单，容易判断任意两个顶点之间是否有边，也容易计算顶点的度。
- 缺点：存储空间为 $O(n^2)$，对于稀疏图（边数较少）会浪费大量的空间。适用于边稠密的图。
2. 邻接表 (Adjacency List) 表示法
邻接表是一种链式存储结构，为图中的每个顶点建立一个单链表。
- 结构组成：
- 表头结点表：采用顺序存储结构，记录顶点信息以及指向该顶点第一个邻接点的指针。
- 边表（弧表）：链表中的结点。每个结点记录邻接顶点在表头数组中的下标、边权（若有），以及指向下一个边结点的指针。
- 有向图的分类：
- 邻接表：链表中记录的是顶点的出边（便于求出度）。
- 逆邻接表：链表中记录的是顶点的入边（便于求入度）。
- 空间复杂度： 对于含有 $n$ 个顶点和 $e$ 条边的无向图，需要 $n$ 个头结点和 $2e$ 个表结点；对于有向图，需要 $n$ 个头结点和 $e$ 个表结点。适用于稀疏图。
5.3 图的遍历 (Graph Traversal)
从图的某个顶点出发，访问图中所有的顶点，且使每个顶点仅被访问一次。常见的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。
1. 深度优先搜索 (Depth First Search, DFS)
- 基本思想：类似于树的先序遍历。从起始顶点 $v$ 出发，访问该顶点，然后访问与 $v$ 邻接且未被访问的顶点 $v_1$；再从 $v_1$ 出发深度优先搜索……当无法继续向下访问时，回溯到前一个顶点，寻找其未被访问的其他邻接点。
- 数据结构：通常使用递归（隐式栈）来实现。
2. 广度优先搜索 (Breadth First Search, BFS)
- 基本思想：类似于树的层次遍历。从起始顶点 $v$ 出发，访问 $v$ 之后，依次访问 $v$ 的所有未被访问的邻接点；然后再按照这些邻接点被访问的先后顺序，依次访问它们各自未被访问的邻接点，直到图中所有顶点都被访问过。
- 数据结构：借助队列来实现。
5.4 最小生成树 (Minimum Spanning Tree, MST)
对于一个连通网（带权连通图），包含全部 $n$ 个顶点，且使其中 $n-1$ 条边上的权值之和达到最小的子图称为最小生成树。
1. 经典算法比较
| 算法名称 | 核心思想 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| Kruskal (克鲁斯卡尔) 算法 | “加边法”：按权值从小到大选择 $n-1$ 条边，要求不能构成回路。 | $O(e \log e)$ | 适用于稀疏图 |
| Prim (普里姆) 算法 | “加点法”：从某一顶点开始，不断选择与当前树相邻且权值最小的边，将其另一端的顶点加入树中。 | $O(n^2)$ | 适用于稠密图 |
5.5 核心算法 C++ 代码实现
以下提供图的存储结构（邻接表）、DFS/BFS 遍历，以及 Kruskal 算法求最小生成树的完整 C++ 实现。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 边的结构体（用于 Kruskal 算法）
struct Edge {
int u, v, weight;
bool operator<(const Edge& other) const {
return weight < other.weight;
}
};
// 图的邻接表类
class Graph {
private:
int numVertices;
vector<vector<pair<int, int>>> adjList; // pair<邻接点, 边权>
public:
Graph(int vertices) {
numVertices = vertices;
adjList.resize(vertices);
}
// 添加无向边
void addEdge(int u, int v, int weight = 1) {
adjList[u].push_back({v, weight});
adjList[v].push_back({u, weight});
}
// 1. 深度优先搜索（DFS）辅助递归函数
void DFSHelper(int v, vector<bool>& visited) {
visited[v] = true;
cout << "v" << v << " ";
for (auto neighbor : adjList[v]) {
int u = neighbor.first;
if (!visited[u]) {
DFSHelper(u, visited);
}
}
}
// 执行 DFS
void DFS(int startVertex) {
vector<bool> visited(numVertices, false);
cout << "DFS 遍历结果: ";
DFSHelper(startVertex, visited);
cout << endl;
}
// 2. 广度优先搜索（BFS）
void BFS(int startVertex) {
vector<bool> visited(numVertices, false);
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
cout << "BFS 遍历结果: ";
while (!q.empty()) {
int v = q.front();
q.pop();
cout << "v" << v << " ";
for (auto neighbor : adjList[v]) {
int u = neighbor.first;
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
cout << endl;
}
};
// 3. 并查集结构体（Kruskal 算法的连通性判断）
struct DisjointSet {
vector<int> parent;
DisjointSet(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]); // 路径压缩
}
bool unite(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
parent[rootI] = rootJ;
return true;
}
return false;
}
};
// 4. Kruskal 算法求最小生成树
void KruskalMST(int vertices, vector<Edge>& edges) {
sort(edges.begin(), edges.end()); // 边权从小到大排序
DisjointSet ds(vertices);
vector<Edge> mst;
int mstWeight = 0;
for (const auto& edge : edges) {
if (ds.unite(edge.u, edge.v)) {
mst.push_back(edge);
mstWeight += edge.weight;
}
}
cout << "Kruskal 最小生成树边集: " << endl;
for (const auto& edge : mst) {
cout << "v" << edge.u << " - v" << edge.v << " : " << edge.weight << endl;
}
cout << "最小生成树总权值和为: " << mstWeight << endl;
}
int main() {
// 构建图结构
Graph g(6);
g.addEdge(0, 1, 6);
g.addEdge(0, 2, 1);
g.addEdge(0, 3, 5);
g.addEdge(1, 2, 5);
g.addEdge(1, 4, 3);
g.addEdge(2, 3, 5);
g.addEdge(2, 4, 6);
g.addEdge(2, 5, 4);
g.addEdge(3, 5, 2);
g.addEdge(4, 5, 6);
g.DFS(0);
g.BFS(0);
// 最小生成树测试数据
vector<Edge> edges = {
{0, 1, 6}, {0, 2, 1}, {0, 3, 5},
{1, 2, 5}, {1, 4, 3}, {2, 3, 5},
{2, 4, 6}, {2, 5, 4}, {3, 5, 2},
{4, 5, 6}
};
KruskalMST(6, edges);
return 0;
}
5.6 练习题集
一、 填空题
- 设无向图 $G$ 中顶点数为 $n$，则图 $G$ 至少有______条边，至多有______条边；若 $G$ 为有向图，则至少有______条边，至多有______条边。
- 图的存储结构主要有两种，分别是______和______。
- 已知一个有向图的邻接矩阵表示，计算第 $j$ 个顶点的入度的方法是______。
- 有向图 $G$ 用邻接矩阵 $A[n][n]$ 存储，其第 $i$ 行的所有元素之和等于顶点 $v_i$ 的______。
- $n$ 个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。
- 表示一个有 $100$ 个顶点，$1000$ 条边的有向图的邻接矩阵有______个非零矩阵元素。
- 无向图中所有顶点的度数之和等于所有边数的______倍。
- 具有 $n$ 个顶点的无向完全图中包含有______条边，具有 $n$ 个顶点的有向完全图中包含有______条边。
- 一个具有 $n$ 个顶点的无向图中，要连通所有顶点则至少需要______条边。
- 对于一个具有 $n$ 个顶点和 $e$ 条边的连通图，其生成树中的顶点数和边数分别为______和______。
- 对于一个图 $G$ 的遍历，通常有两种方法，它们分别是______和______。
二、 选择题
-
在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4
-
含 $n$ 个顶点的连通图中的任意一条简单路径，其长度（路径上的边数）不可能超过（ ）。 A. 1 B. $n/2$ C. $n-1$ D. $n$
-
对于一个具有 $n$ 个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。 A. $n$ B. $(n-1)^2$ C. $n-1$ D. $n^2$
-
关于图的生成树，下列说法正确的是（ ），$n$ 个顶点的生成树有（ ）条边。 A. 唯一 B. 不唯一 C. 唯一性不能确定 D. $n$ E. $n+1$ F. $n-1$
-
【NOIP 2019 提高组】 $G$ 是一个非连通无向图（无重边和自环），共有 $28$ 条边，则该图至少有（ ）个顶点。 A. 6 B. 7 C. 8 D. 9
-
最小生成树指的是（ ）。 A. 由连通网所得到的边数最少的生成树 B. 由连通网所得到的顶点数相对较少的生成树 C. 连通网中所有生成树中权值之和为最小的生成树 D. 连通网的极小连通子图
-
某无向图的邻接矩阵 $A$ 大小为 $3 \times 3$ 且对角线元素全为 $0$，非对角线元素不全为 $0$，可以看出，该图共有（ ）个顶点。 A. 3 /B. 6 C. 9 D. 以上答案均不正确
-
在一个具有 $n$ 个顶点的有向完全图中包含有（ ）条边。 A. $\frac{n(n-1)}{2}$ B. $n(n-1)$ C. $\frac{n(n+1)}{2}$ D. $n^2$
-
在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 4
-
具有 $4$ 个顶点的无向完全图有（ ）条边。 A. 6 B. 12 C. 16 D. 20
-
具有 $6$ 个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8
-
$n$ 个结点的完全有向图含有边的数目为（ ）。 A. $n^2$ B. $n(n+1)$ C. $n/2$ D. $n(n-1)$
-
有向图中一个顶点的度是该顶点的（ ）。 A. 入度 B. 出度 C. 入度与出度之和 D. (入度+出度)/2
-
在含 $n$ 个顶点和 $e$ 条边的无向图的邻接矩阵中，零元素的个数为（ ）。 A. $e$ B. $2e$ C. $n^2 - e$ D. $n^2 - 2e$
5.7 练习题答案与详细解析
一、 填空题 答案及解析
- $0$，$\frac{n(n-1)}{2}$，$0$，$n(n-1)$
- 解析：无向图边集可为空（最少为 0 边），无向完全图边数最大为 $\frac{n(n-1)}{2}$；有向图最少为 0，最大（有向完全图）边数（弧数）为 $n(n-1)$。
- 邻接矩阵，邻接表
- 解析：图的常见存储结构为二维数组（对稠密图更优的邻接矩阵）以及链式结构（对稀疏图更优的邻接表）。
- 求第 $j$ 列的所有元素之和
- 解析：有向图邻接矩阵中，第 $j$ 列代表所有指向顶点 $v_j$ 的有向边，其和即为 $v_j$ 的入度。
- 出度
- 解析：第 $i$ 行元素表示以 $v_i$ 为起点的有向边。这一行各元素值之和即为 $v_i$ 的出度。
- $2(n-1)$
- 解析：$n$ 个顶点的连通无向图最少需要 $n-1$ 条边。在邻接矩阵中，因为无向图的边是对称存储的，每条边对应两个非零元素，因此邻接矩阵中非零元素个数至少为 $2(n-1)$。
- $1000$
- 解析：有向图的一条边在邻接矩阵中只需占用一个非零元素位置，因此 $1000$ 条边对应 $1000$ 个非零元。
- $2$
- 解析：每一条无向边均与两个顶点相连，因此会为图的总度数贡献 2，故所有顶点的度数之和等于边数的 2 倍。
- $\frac{n(n-1)}{2}$，$n(n-1)$
- 解析：基本概念结论，分别对应完全无向图与完全有向图的最大边数。
- $n-1$
- 解析：连通 $n$ 个顶点的无向极小连通图是一棵树，所含的边数为 $n-1$ 条。
- $n$，$n-1$
- 解析：根据生成树定义，生成树必须包含原图的全部 $n$ 个顶点，且是用极小无回路的 $n-1$ 条边来保持连通。
- 深度优先搜索（DFS），广度优先搜索（BFS）
二、 选择题 答案及解析
- C
- 解析：根据定理，度数之和 $= 2 \times$ 边数。
- C
- 解析：简单路径中没有重复顶点。包含 $n$ 个顶点的连通图，简单路径上最多包含所有的 $n$ 个顶点，此时路径上的边数为 $n-1$ 条。
- D
- 解析：邻接矩阵是大小为 $n \times n$ 的二维数组，共包含 $n^2$ 个元素。
- C，F
- 解析：对于连通网，最小生成树一般不唯一（若各边权值不相同则唯一，这里是一般生成树）；生成树所含边数固定为 $n-1$ 条。
- D
- 解析：要让顶点数最少，应尽可能将 $28$ 条边放入一个完全无向图（连通的子图）中，最后再加上一个孤立顶点使其成为非连通图。 设连通子图有 $k$ 个顶点，其最多能容纳的边数为 $\frac{k(k-1)}{2}$ 条。 令 $\frac{k(k-1)}{2} \ge 28 \implies k(k-1) \ge 56$，解得 $k \ge 8$（因为 $8 \times 7 = 56$）。 这 $8$ 个顶点构成一个完全图能提供 28 条边。为使其非连通，需要再增加至少 1 个孤立顶点。所以该非连通图至少含有 $8 + 1 = 9$ 个顶点。
- C
- 解析：生成树权值之和最小即为最小生成树（MST）。
- A
- 解析：邻接矩阵的大小为 $n \times n$，其行数和列数即为顶点的个数。由于 $A$ 是 $3 \times 3$ 的矩阵，因此顶点数为 3。
- B
- 解析：完全有向图的边数公式为 $n(n-1)$。
- C
- 解析：任何图中，所有顶点的度数之和均为边数 $e$ 的 2 倍。
- A
- 解析：$\frac{4 \times (4 - 1)}{2} = 6$ 条。
- A
- 解析：具有 $n$ 个顶点的图，要确保能成为连通图，最少应具有极小连通子图（树）的边数，即 $n-1$ 条边。对于 6 个顶点的图，至少需要 5 条边才能确保其连通（一条链形式）。
- D
- 解析：完全有向图含有 $n(n-1)$ 条弧。
- C
- 解析：有向图中，顶点的度定义为指向该顶点的边（入度）和从该顶点指出的边（出度）之和。
- D
- 解析：大小为 $n \times n$ 的邻接矩阵一共有 $n^2$ 个元素。由于这是一个无向图，每条无向边在矩阵中对称记录两次（即占用 2 个非零元位置），非零元素总数为 $2e$。因此零元素的个数为 $n^2 - 2e$。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
