图的存储与定义
知识总结
图的基本概念
- 图 G = (V, E)：V是顶点集合，E是边集合
- 有向图：边有方向，(u, v) 表示u到v的边
- 无向图：边没有方向，{u, v} 表示u和v之间的边
- 带权图：边上有权值（距离、费用等）
基本术语
| 术语 | 定义 |
|---|---|
| 度 | 与该顶点相关联的边数 |
| 入度 | 有向图中指向该顶点的边数 |
| 出度 | 有向图中从该顶点出发的边数 |
| 路径 | 从一个顶点到另一个顶点经过的边序列 |
| 环/回路 | 起点和终点相同的路径 |
| 简单路径 | 不经过重复顶点的路径 |
重要性质
- 无向图：所有顶点度之和 = 2 × 边数
- 有向图：所有顶点入度之和 = 所有顶点出度之和 = 边数
- n个顶点的完全图有 n(n-1)/2 条边（无向）或 n(n-1) 条边（有向）
图的存储方式
邻接矩阵
int G[N][N]; // G[i][j] = 1 表示i到j有边- 空间：O(n²)
- 查询边：O(1)
- 适合稠密图
邻接表
vector<int> adj[N]; // adj[i] 存储i的所有邻居- 空间：O(n + m)
- 适合稀疏图