树只是图的一种特殊情况——去掉"不能有环、必须连通"这些限制，就得到了更一般的图。存好图，是后面最短路、生成树这些算法的第一步。
11.1 节讲过，树是"连通、没有环"的一种特殊结构——任意两个节点之间只有一条唯一的路径。如果去掉这些限制：允许存在环，允许一个节点连着好几条能到达同一个地方的路，甚至允许某些节点之间根本无法互相到达——就得到了更一般的结构：图（Graph）。图论要研究的问题（怎么找最短路、怎么用最少的边连通所有点……）都是建立在"图存好了"这个前提之上的，本节就是图论的第一课：怎么把一张图存进程序里。
一张图由顶点（节点）和边组成，记作 G = (V, E)。围绕"边"有几组基本分类，贯穿整个图论部分：
| 分类 | 含义 |
|---|---|
| 无向图 / 有向图 | 无向图的边没有方向（A-B 和 B-A 是同一条边）；有向图的边有方向（A→B 不代表 B→A 也存在） |
| 带权图 / 无权图 | 带权图的每条边有一个数值（比如距离、代价）；无权图的边只表示"连通"，没有额外数值 |
| 简单图 | 没有自环（自己连自己）、没有重边（两点之间不止一条边）的图；本节的例子都是简单图 |
本节统一用这张无向带权图做例子（4 个顶点，5 条边）：
A-B(4)、A-C(1)、B-C(2)、B-D(5)、C-D(8)。下面用两种不同的方式把这张图存进程序里。邻接矩阵：开一个 V×V 的二维数组 g，g[i][j] 直接存"顶点 i 到顶点 j 这条边的权值"；如果两点之间没有边，就存一个"不可能出现的数"（通常用一个很大的数表示，记作 INF，代表"不可达"）。
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 4 | 1 | INF |
| B | 4 | 0 | 2 | 5 |
| C | 1 | 2 | 0 | 8 |
| D | INF | 5 | 8 | 0 |
g[A][B] 和 g[B][A] 存的是同一条边，值相等。对角线上 g[i][i]=0 表示"自己到自己"距离为 0；A-D 之间没有直接的边，存 INF，而不是 0（0 会被误认为"存在一条权值为 0 的边"）。| 1 | const int INF = 0x3f3f3f3f; |
| 2 | int g[MAXN][MAXN]; // g[i][j]：i 到 j 这条边的权值，INF 表示没有边 |
| 3 | |
| 4 | void InitGraph(int n) |
| 5 | { |
| 6 | for (int i = 1; i <= n; i++) |
| 7 | for (int j = 1; j <= n; j++) |
| 8 | g[i][j] = (i == j) ? 0 : INF; // ★ 默认全部设成 INF（不可达），对角线是 0 |
| 9 | } |
| 10 | |
| 11 | void AddEdge(int u, int v, int w) |
| 12 | { |
| 13 | g[u][v] = w; |
| 14 | g[v][u] = w; // 无向图：两个方向都要存；有向图只存 g[u][v] 这一个方向 |
| 15 | } |
邻接表：给每个顶点开一个"列表"，只记录它真正连着的那些邻居（以及边权），而不是像矩阵那样把"所有顶点两两之间"的关系都存一遍。C++ 里最方便的写法是每个顶点对应一个 vector，存"邻居编号 + 边权"这一对信息。
A 只存了 (B,4)、(C,1) 两项，完全不需要提到"A 和 D 没有边"这件事。这正是邻接表比邻接矩阵省空间的原因：矩阵会把"没有边"的关系也存一遍（存成 INF），邻接表则压根不提。| 1 | vector<pair<int,int>> adj[MAXN]; // adj[u] 里的每一项 (v, w) 表示 u 到 v 有一条权值为 w 的边 |
| 2 | |
| 3 | void AddEdge(int u, int v, int w) |
| 4 | { |
| 5 | adj[u].push_back({v, w}); |
| 6 | adj[v].push_back({u, w}); // 无向图：两个方向各存一次；有向图只存这一行 |
| 7 | } |
| 8 | |
| 9 | // 遍历顶点 u 的所有邻居： |
| 10 | for (auto [v, w] : adj[u]) |
| 11 | cout << "邻居 " << v << "，边权 " << w << endl; |
关键看图稀疏还是稠密——顶点数是 V，边数是 E：
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间开销 | O(V²)，不管边多边少都要开这么大 | O(V+E)，只存真正存在的边 |
| 查询"u、v 之间有没有边" | O(1)，直接看 g[u][v] | O(度数)，要遍历 u 的邻居列表 |
| 遍历"u 的所有邻居" | O(V)，要扫一整行（哪怕大部分是 INF） | O(度数)，只遍历真正的邻居，不浪费 |
| 适合场景 | 顶点数较少、边很稠密（接近 V² 条边） | 顶点数较多、边比较稀疏（远小于 V² 条边） |
A-B 其实包含"A 能到 B"和"B 能到 A"两条信息，邻接矩阵要设置 g[A][B] 和 g[B][A] 两个位置，邻接表要往 adj[A] 和 adj[B] 各插入一次——只存一个方向，会导致后续算法（比如从 B 出发做 BFS/DFS）漏掉这条边，图变成"看起来"是有向的。INF）表示，而不是 0——如果题目里真的存在权值为 0 的边，用 0 表示"不可达"会让程序把这条边误判成"没有这条边"，或者反过来把"不可达"误判成"有一条权值为 0 的边"，后续最短路算法全盘出错。AddEdge 里改成 g[u][v] = min(g[u][v], w)；邻接表天然支持重边（每条边都是列表里单独的一项），但涉及自环时要注意部分算法（比如后面的最小生成树）可能需要提前把自环过滤掉。