图的基本概念
**图（Graph）由顶点（Vertex）和边（Edge）**组成，用来表达多对多关系：社交网络、道路导航、 任务依赖、电路连接都可以抽象成图。
相对树：树是特殊的连通无环图；图可以有环、可以不连通、顶点之间可以任意相连。
本文解决什么问题
- 有向 / 无向、带权、连通等基本术语
- 度、路径、环的含义
- 本章后续各篇学什么
基本分类
| 概念 | 含义 |
|---|---|
| 无向图 | 边无方向， 与 相同 |
| 有向图 | 边有方向， |
| 带权图 | 边带代价（距离、耗时、费用） |
| 简单图 | 无自环、无重边（教材默认常如此） |
| 稀疏 / 稠密 | 边少 / 边接近 量级 |
常用术语
| 术语 | 含义 |
|---|---|
| 度 | 无向图：与顶点相连的边数；有向图分出度 / 入度 |
| 路径 | 顶点序列，相邻者有边 |
| 环 | 起点终点相同的路径（简单环不重复顶点） |
| 连通 | 无向图中任意两点有路径 |
| 强连通 | 有向图中任意两点互相可达 |
| 连通分量 | 极大连通子图 |
| 生成树 | 包含全部顶点的无环连通子图 |
无向图：边数之和等于度数之和的一半（握手引理）。有向图：所有出度之和 = 所有入度之和 = 边数。
本章地图
| 文章 | 内容 |
|---|---|
| 图的存储结构 | 邻接矩阵 / 邻接表 |
| 图的遍历 | DFS / BFS |
| 最短路径 | BFS / Dijkstra 等 |
| 最小生成树 | Prim / Kruskal |
| 拓扑排序 | DAG 上的线性序 |
建模直觉
把业务对象当顶点、关系当边：
- fort 之间的道路 → 无向带权图
- 课程先修 → 有向图，常做拓扑排序
- 网页链接 → 有向图
先画对图，再选存储与算法，比一上来背模板更重要。
小结
图描述任意连接关系。先分清有向/无向、是否带权、是否连通，再进入存储与遍历。
下一篇：图的存储结构。