算法竞赛中的数据结构：图

目录

• 一.图的基本概念
• • 1.图的定义
  • 2.图、树、线性表的联系与区别
  • • 2.1 核心联系
      • 2.2 核心区别
• 二.图的分类
• • 1.按边的方向分类
  • 2.按边的权重分类
  • 3 .按顶点和边的数量分类
  • 4 .按连通性分类（针对无向图）
  • 5 .按强连通性分类（针对有向图）
  • 6 .其他特殊类型
  • 7.顶点的度(补充)
  • 8.路径及相关长度概念（补充）
  • • 8.1 路径
      • 8.2 路径长度（无权图）
      • 8.3 带权路径长度（带权图）
      • 8.4 核心区别对比
• 三.邻接矩阵
• • 1.邻接矩阵
  • • 【注意】
• 四.邻接表
• 五.链式前向星

Hello，小伙伴们！又到了咱们一起捣鼓代码的时间啦！💪 把生活调成热情模式，带着满满的能量钻进编程的奇妙世界吧——今天也要写出超酷的代码，冲鸭！🚀

我的博客主页：喜欢吃燃面
我的专栏：《C语言》，《C语言之数据结构》，《C++》，《Linux学习笔记》
感谢你点开这篇博客呀！真心希望这些内容能给你带来实实在在的帮助～ 如果你有任何想法或疑问，非常欢迎一起交流探讨，咱们互相学习、共同进步，在编程路上结伴成长呀！

一.图的基本概念

1.图的定义

图（Graph） 是一种非线性的数据结构，由顶点集合（Vertex） 和边集合（Edge） 组成，用于表示多个对象之间的多对多关系。

其形式化定义为：
一个图 G GG 可以表示为二元组 G = ( V , E ) G=(V, E)G=(V,E)

• V VV 是非空的顶点集合，其中的每个元素称为顶点（或节点），记为 v i v_ivi​；
• E EE 是边的集合，其中的每个元素称为边，记为 e j e_jej​，边用于连接 V VV 中的两个顶点。

2.图、树、线性表的联系与区别

三者都属于数据结构，核心是存储数据及数据间的关系，且线性表 ⊂ 树 ⊂ 图，是从简单到复杂、从一对一到多对多的关系扩展。

2.1 核心联系

1. 包含关系
   • 线性表是最简单的结构，可以看作是特殊的树（树中每个节点只有一个子节点，退化为线性表）。
   • 树是特殊的图：树是无环的连通无向图，且满足 “n个顶点对应n-1条边” 的条件。
2. 遍历逻辑相通
   三者的遍历都依赖迭代或递归，比如线性表的顺序遍历、树的深度优先遍历、图的深度优先遍历，核心思想都是“按规则访问每个元素一次”。

2.2 核心区别

1. 关系复杂度不同
   • 线性表：一对一，像排队的人，每个人只和前后的人有关系。
   • 树：一对多，像家族族谱，一个父节点可以有多个子节点，但不能反过来。
   • 图：多对多，像城市交通网，任意两个城市之间可以有道路，还能有环路。
2. 结构约束不同
   • 线性表必须是线性的、无分支。
   • 树必须无环，且只有一个根节点。
   • 图可以有环、有多个孤立顶点，没有根节点的概念。

二.图的分类

1.按边的方向分类

1.1 无向图

• 边没有方向，连接顶点 u uu 和 v vv 的边记为 ( u , v ) (u,v)(u,v)，且 ( u , v ) = ( v , u ) (u,v) = (v,u)(u,v)=(v,u)。
• 示例：无向社交网络（A和B是朋友等价于B和A是朋友）、双向公路地图。

1.2 有向图

• 边有方向，连接顶点 u uu 到 v vv 的边记为 < u , v > <u,v><u,v>， u uu 是起点， v vv 是终点，且 < u , v > ≠ < v , u > <u,v> \neq <v,u><u,v>=<v,u>。
• 示例：有向社交关注（A关注B不等于B关注A）、单行道地图、任务依赖关系。

2.按边的权重分类

2.1 无权图

• 边仅表示顶点间的连接关系，没有附加数值。
• 示例：仅记录“是否相连”的拓扑图。

2.2 带权图（网）

• 每条边都带有一个数值权重（如距离、成本、时间）。
• 示例：带距离的城市交通图、带成本的通信网络。

3 .按顶点和边的数量分类

3.1 稀疏图

• 边数远小于顶点数的平方（ E ≪ V 2 E \ll V^2E≪V2），顶点间连接稀疏。
• 示例：现实中的社交网络、路网。

3.2 稠密图

• 边数接近顶点数的平方（ E ≈ V 2 E \approx V^2E≈V2），顶点间连接紧密。
• 示例：完全图、稠密的通信拓扑。

3.3 完全图

• 无向完全图：任意两个顶点间都有一条边，边数为 V ( V − 1 ) 2 \frac{V(V-1)}{2}2V(V−1)​。
• 有向完全图：任意两个顶点间都有两条方向相反的边，边数为 V ( V − 1 ) V(V-1)V(V−1)。

4 .按连通性分类（针对无向图）

4.1 连通图

• 任意两个顶点之间都存在路径，整个图是一个连通分量。

4.2 非连通图

• 存在至少两个顶点之间没有路径，图包含多个连通分量。

5 .按强连通性分类（针对有向图）

5.1 强连通图

• 任意两个顶点 u uu 和 v vv 之间，既存在 u uu 到 v vv 的路径，也存在 v vv 到 u uu 的路径。

5.2 弱连通图

• 将有向边改为无向边后是连通图，但本身不是强连通图。

5.3 非连通图

• 将有向边改为无向边后仍是非连通图。

6 .其他特殊类型

6.1 无环图

• 不包含环路的图，常见的如 有向无环图（DAG），用于表示任务调度、表达式求值等。

6.2 二分图

• 顶点可分为两个不相交的集合，每条边的两个顶点分别属于不同集合，无同集合内的边。
• 示例：用户-商品的购买关系图。

7.顶点的度(补充)

顶点的度是衡量顶点与其他顶点连接紧密程度的指标，在无向图和有向图中的定义不同。

1. 无向图中的度
   一个顶点的度 = 与该顶点相连的边的数量，记为 d ( v ) d(v)d(v)。
   • 示例：无向图中顶点 A AA 连接了 3 条边，则 d ( A ) = 3 d(A)=3d(A)=3。
   • 性质：无向图所有顶点的度之和 = 2 × 2 \times2× 边数（每条边贡献 2 个度）。
2. 有向图中的度
   有向图的度分为入度和出度，两者之和为顶点的总度。
   • 入度（ d i n ( v ) d_{in}(v)din​(v)）：以该顶点为终点的有向边数量。
   • 出度（ d o u t ( v ) d_{out}(v)dout​(v)）：以该顶点为起点的有向边数量。
   • 性质：有向图所有顶点的入度之和 = 所有顶点的出度之和 = 边数。

8.路径及相关长度概念（补充）

8.1 路径

路径是图中从一个顶点到另一个顶点的顶点序列，核心定义与属性如下：

1. 定义
   给定图 G = ( V , E ) G=(V,E)G=(V,E)，从顶点 v 0 v_0v0​ 到 v k v_kvk​ 的路径是一个顶点序列 v 0 , v 1 , v 2 , . . . , v k v_0,v_1,v_2,...,v_kv0​,v1​,v2​,...,vk​，满足任意相邻两个顶点 v i − 1 v_{i-1}vi−1​ 和 v i v_ivi​ 之间都有边相连。
2. 关键属性
   • 路径长度：路径中包含的边的数量。
   • 简单路径：路径中所有顶点不重复出现（无环路）。
   • 回路（环）：起点和终点为同一个顶点的路径；若除起点终点外其他顶点不重复，则称为简单回路。
3. 示例
   • 无向图中顶点序列 A → B → C A \to B \to CA→B→C 是一条简单路径，长度为 2。
   • 序列 A → B → C → A A \to B \to C \to AA→B→C→A 是一条简单回路，长度为 3。

8.2 路径长度（无权图）

1. 定义：在无权图中，路径长度指路径中包含的边的数量，与边的权重无关。
2. 计算公式：若路径顶点序列为 v 0 → v 1 → v 2 → ⋯ → v k v_0 \to v_1 \to v_2 \to \dots \to v_kv0​→v1​→v2​→⋯→vk​，则路径长度 = k kk。
3. 示例：无向图中路径 A → B → C A \to B \to CA→B→C 包含 2 条边，路径长度为 2；回路 A → B → C → A A \to B \to C \to AA→B→C→A 包含 3 条边，路径长度为 3。

8.3 带权路径长度（带权图）

1. 定义：在带权图（网）中，带权路径长度指路径中所有边的权重之和，是带权图的核心指标。
2. 计算公式：若路径顶点序列为 v 0 → v 1 → v 2 → ⋯ → v k v_0 \to v_1 \to v_2 \to \dots \to v_kv0​→v1​→v2​→⋯→vk​，每条边的权重为 w ( v i − 1 , v i ) w(v_{i-1},v_i)w(vi−1​,vi​)，则带权路径长度 = ∑ i = 1 k w ( v i − 1 , v i ) \sum_{i=1}^k w(v_{i-1},v_i)∑i=1k​w(vi−1​,vi​)。
3. 示例：带权图中路径 A → B → C A \to B \to CA→B→C 的边权重分别为 w ( A , B ) = 3 w(A,B)=3w(A,B)=3、 w ( B , C ) = 5 w(B,C)=5w(B,C)=5，则带权路径长度 = 3 + 5 = 8 3+5=83+5=8。

8.4 核心区别对比

三.邻接矩阵

1.邻接矩阵

邻接矩阵，指用一个矩阵（即二维数组）存储图中边的信息（即各个顶点之间的邻接关系），存储顶点之间邻接关系的矩阵称为邻接矩阵。

对于带权图而言，若顶点 v i v_ivi​ 和 v j v_jvj​ 之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点 v i v_ivi​ 和 v j v_jvj​ 不相连，则用 ∞ \infty∞ 来代表这两个顶点之间不存在边。

对于不带权的图，可以创建一个二维的 bool 类型的数组，来标记顶点 v i v_ivi​ 和 v j v_jvj​ 之间有边相连。

【注意】

矩阵中元素个数为 n 2 n^2n2，即空间复杂度为 O ( n 2 ) O(n^2)O(n2)， n nn 为顶点个数，和实际边的条数无关，适合存储稠密图。

1#include<iostream>
2#include<cstring>
3#include<queue>
4using namespace std;
5
6const int N = 110;
7
8// 邻接矩阵存储定义
9int edges[N][N];  // edges[a][b]表示a到b的边权（-1表示无边）
10int n, m;         // n：顶点数，m：边数
11bool st[N];       // 访问标记数组
12
13
14// 邻接矩阵版DFS
15void dfs_matrix(int u)
16{
17	cout << u << endl;
18	st[u] = true;
19	// 遍历所有邻接顶点（1~n）
20	for (int v = 1; v <= n; v++)
21	{
22		if (edges[u][v] != -1 && !st[v])
23			dfs_matrix(v);
24	}
25}
26
27
28// 邻接矩阵版BFS
29void bfs_matrix(int u)
30{
31	queue<int> q;
32	q.push(u);
33	st[u] = true;
34	while (q.size())
35	{
36		auto a = q.front();
37		q.pop();
38		cout << a << endl;
39		// 遍历所有邻接顶点（1~n）
40		for (int b = 1; b <= n; b++)
41		{
42			if (edges[a][b] != -1 && !st[b])
43			{
44				q.push(b);
45				st[b] = true;
46			}
47		}
48	}
49}
50
51
52// 邻接矩阵初始化
53int main()
54{
55	memset(edges, -1, sizeof(edges)); // 初始化：-1表示无边
56	cin >> n >> m;
57	// 输入边数据
58	for (int i = 1; i <= m; i++)
59	{
60		int a, b, value;
61		cin >> a >> b >> value;
62		edges[a][b] = value;
63		// 无向图需添加：edges[b][a] = value;
64	}
65
66	// 测试遍历
67	cout << "邻接矩阵DFS结果：" << endl;
68	dfs_matrix(1);
69	memset(st, false, sizeof(st)); // 重置标记
70
71	cout << "\n邻接矩阵BFS结果：" << endl;
72	bfs_matrix(1);
73	return 0;
74}
75

四.邻接表

不懂邻接表和链式前向星请查看：算法竞赛中的树

1#include<iostream>
2#include<cstring>
3#include<vector>
4#include<queue>
5using namespace std;
6
7const int N = 110;
8
9// 邻接表存储定义
10typedef pair<int, int> PII;       // <邻接顶点, 边权>
11vector<PII> edges_list[N];        // edges_list[a]存储a的所有邻接边
12int n, m;
13bool st[N];
14
15
16// 邻接表版DFS
17void dfs_list(int u)
18{
19	cout << u << endl;
20	st[u] = true;
21	// 遍历u的所有邻接边
22	for (auto &e : edges_list[u])
23	{
24		int v = e.first;
25		if (!st[v])
26			dfs_list(v);
27	}
28}
29
30
31// 邻接表版BFS
32void bfs_list(int u)
33{
34	queue<int> q;
35	q.push(u);
36	st[u] = true;
37	while (q.size())
38	{
39		auto a = q.front();
40		q.pop();
41		cout << a << endl;
42		// 遍历a的所有邻接边
43		for (auto &e : edges_list[a])
44		{
45			int b = e.first;
46			if (!st[b])
47			{
48				q.push(b);
49				st[b] = true;
50			}
51		}
52	}
53}
54
55
56// 邻接表初始化
57int main()
58{
59	cin >> n >> m;
60	// 输入边数据
61	for (int i = 1; i <= m; i++)
62	{
63		int a, b, value;
64		cin >> a >> b >> value;
65		edges_list[a].push_back({b, value});
66		// 无向图需添加：edges_list[b].push_back({a, value});
67	}
68
69	// 测试遍历
70	cout << "邻接表DFS结果：" << endl;
71	dfs_list(1);
72	memset(st, false, sizeof(st));
73
74	cout << "\n邻接表BFS结果：" << endl;
75	bfs_list(1);
76	return 0;
77}
78

五.链式前向星

1#include<iostream>
2#include<cstring>
3#include<queue>
4using namespace std;
5
6const int N = 110;
7
8// 链式前向星存储定义
9int h[N];       // h[a]：a的第一条边的编号
10int e[N * 2];   // e[id]：编号id的边的终点
11int ne[N * 2];  // ne[id]：编号id的边的下一条边
12int w[N * 2];   // w[id]：编号id的边的权值
13int id;         // 边的自增编号
14int n, m;
15bool st[N];
16
17
18// 链式前向星添加边
19void add(int a, int b, int value = 0)
20{
21	e[++id] = b;
22	w[id] = value;
23	ne[id] = h[a];
24	h[a] = id;
25}
26
27
28// 链式前向星版DFS
29void dfs_star(int u)
30{
31	cout << u << endl;
32	st[u] = true;
33	// 遍历u的所有边
34	for (int i = h[u]; i; i = ne[i])
35	{
36		int v = e[i];
37		if (!st[v])
38			dfs_star(v);
39	}
40}
41
42
43// 链式前向星版BFS
44void bfs_star(int u)
45{
46	queue<int> q;
47	q.push(u);
48	st[u] = true;
49	while (q.size())
50	{
51		auto a = q.front();
52		q.pop();
53		cout << a << endl;
54		// 遍历a的所有边
55		for (int i = h[a]; i; i = ne[i])
56		{
57			int b = e[i];
58			if (!st[b])
59			{
60				q.push(b);
61				st[b] = true;
62			}
63		}
64	}
65}
66
67
68// 链式前向星初始化
69int main()
70{
71	memset(h, 0, sizeof(h)); // 初始化头节点数组为0
72	cin >> n >> m;
73	// 输入边数据
74	for (int i = 1; i <= m; i++)
75	{
76		int a, b, value;
77		cin >> a >> b >> value;
78		add(a, b, value);
79		// 无向图需添加：add(b, a, value);
80	}
81
82	// 测试遍历
83	cout << "链式前向星DFS结果：" << endl;
84	dfs_star(1);
85	memset(st, false, sizeof(st));
86
87	cout << "\n链式前向星BFS结果：" << endl;
88	bfs_star(1);
89	return 0;
90}
91

《算法竞赛中的数据结构：图》 是转载文章，点击查看原文。