在ACM算法竞赛中，图论问题占据了相当重要的地位。无论是基础的遍历、最短路、最小生成树，还是复杂的网络流、连通分量，都离不开对图论知识。本文聚焦于图论中常见术语的解释和图的几种储存方式进行详细阐述，适合希望在算法竞赛图论部分有良好开始的读者。
一、图的基本概念
1.什么是图
图（graph）是由顶点集合和顶点之间的关系（边）组成的一种数据结构：G(V, E)。其中顶点集合V={x|x属于某个数据对象集}是有穷非空集合；E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合，也叫做边的集合。(x, y)表示x到y的一条双向通路，即(x, y)是无方向的；Path(x, y)表示从x到y的一条单向通路，即Path(x, y)是有方向的。
图中的节点成为顶点，第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边，图中的第k条边记作ek，ek = (vi，vj)或<vi，vj>。
2.图的种类
图分为有向图和无向图两种。
有向图中，顶点对<x, y>是有序的，顶点对<x，y>称为顶点x到顶点y的一条边(弧)，<x, y>和<y, x>是两条不同的边。无向图中，顶点对(x, y)是无序的，顶点对(x,y)称为顶点x和顶点y相关联的一条边，这条边没有特定方向，(x, y)和(y，x)是同一条边，无向边(x, y)等于有向边<x, y>和<y, x>。
如图左侧是有向图，右侧是无向图。
3.完全图
在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有两条方向相反的边，则称此图为有向完全图。
如图左侧是有向完全图，右侧是无向完全图：
4.临接顶点
在无向图中G中，若(u, v)是E(G)中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v； 在有向图G中，若<u, v>是E(G)中的一条边，则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。
5.路径
在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
上图从顶点0到顶点4的路径有：
0 2 4
1 1 4
……
可能有很多路径
6.路径长度
对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。
7.简单路径和回路
若路径上各顶点v1，v2，v3，…，vm均不重复，则称这样的路径为简单路径。 若路径上第一个顶点v1和最后一个顶点vm重合，则称这样的路径为回路或环。
8.子图
设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图（即G1的顶点和边都是原图的一部分）。
9.连通图
在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的； 如果图中任意一对顶点都是连通的，则称此图为连通图。
10.强连通图和弱连通图
在有向图中，若每一对顶点vi和vj之间都存在一条从vi到vj的路径，也存在一条从vj到vi的路径，则称此图是强连通图，若每一对顶点vi和vj之间都忽略方向后连通则称此图是弱连通图。
11.生成树
无向图中，一个连通图的最小连通子图称作该图的生成树。
有n个顶点的连通图的生成树有n个顶点和n-1条边。
如下图所示：
右侧两图就是左侧无向图的生成树。
12.顶点的度
对于无向图，顶点的度为依附于该顶点边的条数，用TD(v)来表示，而对于有向图，顶点的度又分为入度和出度，入度是指以该顶点为终点的边的条数，表示为ID(v)；而出度指的是以该顶点为起点的边的条数，表示为OD(v)，有向图的顶点的度的大小就是该顶点的入度和出度之和。
13.带权图
带权图即图上两个连通的顶点的边上有对应权值的图，权值可以是长度也可以是任何相关的单位。
二、图的储存
1.邻接矩阵
邻接矩阵（Adjacency Matrix）适用于稠密图（如n≤1000）、需要快速查询两点间是否有边。空间复杂度是O(n2)，查询两顶点是否有边的时间复杂度是O(1)，由于占用空间太大，不适用于大规模图。
具体核心实现代码如下图所示：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1005; // 最大顶点数
int g[N][N]; // 邻接矩阵，g[u][v] = 权值（无权图可用 0/1）
int n, m; // 顶点数，边数
void add(int u, int v, int w) { // 添加一条有向边 u->v，权值为 w
g[u][v] = w; // 无向图需加 g[v][u] = w
}
int main() {
memset(g, 0, sizeof g); // 初始化为 0（表示无边）
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
// 如果是无向图，取消下面注释：
// add(v, u, w);
}
// 遍历顶点 u 的所有邻接点
int u = 1; // 示例顶点
for (int v = 1; v <= n; v++) {
if (g[u][v] != 0) {
cout << "边 " << u << " -> " << v << " 权值: " << g[u][v] << endl;
}
}
return 0;
}2.邻接表
邻接表（Adjacency List）适用于大多数稀疏图，动态加边方便，代码简洁。对于有权图采用vector<pair<int,int>> g[N]，无权图vector<int> g[N]。
无边权版：
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005; // 最大顶点数
vector<int> g[N]; // g[u] 存储 u 的所有邻接点编号
int n, m;
void add(int u, int v) { // 添加有向边 u->v
g[u].push_back(v);
// 无向图加 g[v].push_back(u);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
add(u, v);
}
// 遍历顶点 u 的邻接点
int u = 1;
for (int v : g[u]) {
cout << "邻接点: " << v << endl;
}
return 0;
}有边权版：
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
vector<pair<int, int>> g[N]; // pair<邻接点, 权值>
int n, m;
void add(int u, int v, int w) {
g[u].emplace_back(v, w); // 用 emplace_back 避免拷贝
// 无向图加 g[v].emplace_back(u, w);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
int u = 1;
for (auto [v, w] : g[u]) { // C++17 结构化绑定
cout << "边 " << u << " -> " << v << " 权值: " << w << endl;
}
return 0;
}3.边集数组
边集数组直接储存边的所有边的信息，适用于需要排序边的算法（如 Kruskal最小生成树）。
实现代码：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int u, v, w;
// 可定义比较函数，便于排序
bool operator<(const Edge& other) const {
return w < other.w; // 按权值升序
}
};
vector<Edge> edges; // 边集数组
int n, m;
void add(int u, int v, int w) {
edges.push_back({u, v, w});
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
// 例如：按权值排序
sort(edges.begin(), edges.end());
// 遍历所有边
for (auto& e : edges) {
cout << e.u << " -> " << e.v << " 权值: " << e.w << endl;
}
return 0;
}4.链式前向星
链式前向星（Linked Forward Star）适用于超大规模图（如n=10⁶，m=10⁷），追求极致效率，静态图构建后不再修改。竞赛中的图的存储经常需要采用链式前向星来实现高效率存储，需要熟悉掌握。
实现代码：
#include <iostream>
using namespace std;
const int N = 100005; // 最大顶点数
const int M = 200005; // 最大边数（无向图需双倍）
struct Edge {
int to, w, nxt; // 终点，权值，下一条边在数组中的下标
} e[M];
int head[N], tot; // head[u] 存储 u 的第一条边编号，tot 为边计数器
void init() { // 初始化（如果有多组数据需要清空）
tot = 0;
for (int i = 1; i < N; i++) head[i] = 0; // 0 表示空，也可用 -1
}
void add(int u, int v, int w) {
e[++tot] = {v, w, head[u]}; // 头插法
head[u] = tot;
}
int main() {
init();
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
// 无向图加 add(v, u, w);
}
// 遍历顶点 u 的所有邻接点
int u = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to, w = e[i].w;
cout << "边 " << u << " -> " << v << " 权值: " << w << endl;
}
return 0;
}对于以上代码的理解还请读者自行查阅资料视频参悟，这里不做过多解释。
