本讲定位：图论系列第一讲，全系列的地基。这一讲解决两件事：题目里画的那堆圈圈和连线怎么放进 C++ 的数组里，以及怎么把它完整地走一遍。之所以把”存”和”走”放在一讲，是因为它们咬得太紧——存法的写法直接决定遍历的写法，而学完存图却不会遍历，一道题也做不了。本讲用实测数据回答三个学生总是含糊过去的问题：邻接矩阵到底 $n$ 多大就存不下（实测 $n=10^4$ 的
int矩阵要 381 MB）、vector邻接表和链式前向星到底谁快（实测建图前向星快 8 倍，遍历 vector 快 29 倍，与流传的”前向星更快”并不一致）、前向星省的那点空间值不值（实测 $n=10^5,m=10^6$ 带权时 23.8 MB vs 29.3 MB）。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，三种存法互相交叉验证 3000 组随机图，B3643 与 P5318 两道例题与洛谷官方样例逐字符核对。前置知识：数组、二维数组、结构体、
vector的push_back与size、递归函数、queue的push/front/pop/empty（见顶层06-linear-structures.md）。不需要任何图论基础，本讲从”什么是点、什么是边”开始。适合对象：CSP-J 复赛备考起步。本讲全部内容标 J，是后面 15 讲的公共前提，没有可跳过的部分。第 4 节的链式前向星如果第一遍看不懂，可以先只用
vector邻接表写题，等到学第 06 讲负环判定或番外 B 网络流时再回来补。
P5318【深基18.例3】查找文献：给一个 $n$ 个点、$m$ 条边的有向图（$n \le 10^5$，$m \le 10^6$），从 1 号点出发，分别输出字典序最小的 DFS 遍历序和 BFS 遍历序。
先不管算法。第一个问题是：这 $10^5$ 个点、$10^6$ 条边，你打算存在哪？
初学者的第一反应几乎总是二维数组：
bool g[100005][100005]; // "第 i 行第 j 列表示 i 到 j 有没有边"
这一行代码在思路上完全正确，但它需要 $10^5 \times 10^5 = 10^{10}$ 个 bool，也就是 9.3 GB。洛谷的内存限制通常是 128 MB 或 256 MB。这份代码不会 WA，会编译都过不了（数组太大）或者直接 MLE——你连”我的算法对不对”这个问题都还没机会问。
而如果换成下面这行，同一张图只要 16.9 MB（实测值，见 5.3）：
vector<int> g[100005]; // g[i] 存 i 的所有出边终点
这就是本讲前半部分存在的理由：图论题的第一个决策点不是选算法，是选存法；而选存法的唯一依据是数据范围。这个决策做错，后面写得再对也没用。
存好之后呢？这道题要求”遍历序”——存进去只是第一步，把它走一遍才有意义。所以本讲后半（第 7 节）会给出 DFS 和 BFS 两份最简模板，第 8.2 节回过头把这道题完整做掉。
| 术语 | 含义 | 在题面里长什么样 |
|---|---|---|
| 点（顶点，vertex/node） | 图里的一个个体 | 城市、路口、文章、人、棋盘上的格子、程序的一个状态 |
| 边（edge） | 两个点之间的一条关系 | 道路、航线、“A 引用了 B”、“A 认识 B”、一步操作 |
| $n$ / $m$ | 点数 / 边数 | 几乎所有图论题的第一行输入 |
| 有向边 | 只能从 $u$ 走到 $v$ | “单行道”、“A 引用 B”、“先修课”、“A 打赢了 B” |
| 无向边 | 两个方向都能走 | “双向道路”、“A 和 B 是朋友”、“用铁路相连” |
| 边权（weight） | 边上带的一个数 | 距离、花费、时间、容量 |
| 度（degree） | 与该点相连的边数 | 无向图：$deg(u)$；有向图分出度与入度 |
| 自环（self-loop） | 起点终点是同一个点的边 | $u = v$ 的输入 |
| 重边（multi-edge） | 两点之间有多条边 | 同一对 $(u,v)$ 输入了多次 |
| 简单图 | 无自环、无重边 | 题面常明说”无重边无自环” |
| 路径 | 一串首尾相接的边 | “从 1 走到 $n$” |
| 连通（无向图） | $u$ 能走到 $v$ | “任意两个城市都能互相到达” |
| 连通块（连通分量） | 极大的互相连通的一坨点 | “有几片湖”“有几个细胞”“分成几个团” |
拿到一道疑似图论题，按顺序问自己三个问题，答案就是建图方案：