图 (Graph)
定义
图是由若干**节点（Vertex）和边（Edge）**构成的数据结构，是对复杂网络关系的抽象。
图可以看作是多叉树结构的延伸——多叉树只允许父节点指向子节点，而图中节点之间可以相互指向，形成更复杂的网络结构。
基本组成
| 组成 | 说明 |
|---|---|
| 节点 (Vertex) | 图的基本组成单元，每个节点有唯一标识 |
| 边 (Edge) | 连接两个节点的线，可以是有向或无向 |
常见类型
按方向分类
- 有向图 (Directed Graph)：边有方向，只能沿箭头方向到达
- 无向图 (Undirected Graph)：边无方向，可双向到达
按权重分类
- 加权图 (Weighted Graph)：边带权重，可表示距离、成本等
- 无权图 (Unweighted Graph)：边无权重
按密度分类
- 稠密图 (Dense Graph)：$E$ 接近 $V^2$，几乎每两个节点间都有边
- 稀疏图 (Sparse Graph)：$E$ 远小于 $V^2$，边很少
存储方式
1. 邻接表 (Adjacency List)
- 每个节点存储一个列表，记录与其相连的所有节点
- 适合稀疏图，空间复杂度 $O(V+E)$
2. 邻接矩阵 (Adjacency Matrix)
- 用 $V \times V$ 的二维数组表示，$matrix[i][j]$ 表示节点 $i$ 到 $j$ 的边
- 适合稠密图，空间复杂度 $O(V^2)$
图 vs 多叉树
| 特性 | 多叉树 | 图 |
|---|---|---|
| 指向关系 | 父 → 子（单向） | 节点间可相互指向 |
| 循环 | 不允许 | 允许 |
| 复杂度 | 较低 | 较高 |
| 应用场景 | 层次结构 | 网络关系 |
核心概念
- 度 (Degree)：无向图中与节点相连的边的条数
- 入度 (Indegree)：有向图中指向该节点的边数
- 出度 (Outdegree)：有向图中从该节点指向其他节点的边数
- 连通性：节点之间是否存在路径
- 子图 (Subgraph)：从原图中删除一些节点和边后得到的图
经典算法
- 二分图算法：判断图是否为二分图
- 拓扑排序：对有向无环图进行线性排序
- 最短路径算法（如 Dijkstra）：找两点间最短路径
- 最小生成树算法（如 Kruskal）：找连接所有节点的最小权重边集合
- 欧拉图算法（如 Hierholzer）：找经过每条边恰好一次的路径/回路，详见 欧拉图基础