一句话理解：图由顶点和边组成，用来表达任意关系。只要对象之间不是严格单父层级，就应该考虑图而不是树。
Unity 中哪些问题是图
- NavMesh 或自定义路点网络
- 任务、配方和技能依赖
- 对话分支
- 房间与传送门连接
- 电力、道路和物流网络
- 状态机转换
图可以是有向或无向、带权或无权，也可能包含环。
邻接表
稀疏图最常用邻接表：每个节点只保存实际相连的边。
使用稳定整数 ID，而不是把临时 GameObject 引用直接写进长期图数据。显示对象可以通过 ID 映射到场景实例。
BFS：无权最短步数
visited 防止在有环图中无限循环。BFS 可以扩展为保存 cameFrom 字典，从而还原最少边数路径。DFS：依赖与循环检测
DFS 适合：
- 遍历连通分量
- 拓扑排序
- 检测有向图中的循环
- 查找所有可能路径
任务依赖或技能前置应当是 DAG。发布配置前要做循环检测，否则可能出现永远无法满足的任务链。
带权路径
当边的 Cost 不同：
- 非负权最短路：Dijkstra
- 有目标启发式：A*
- 所有边同权：BFS
- 存在负权：需要 Bellman-Ford 等专门算法，游戏寻路通常避免负边
A* 的开放集应使用最小堆，而不是每轮对整个 List 排序。
邻接表与邻接矩阵
表示 | 空间 | 检查两点是否相连 | 适合 |
邻接表 | O(V + E) | 取决于邻居数量 | 稀疏游戏图 |
邻接矩阵 | O(V²) | O(1) | 节点少且连接稠密 |
大多数路点、任务依赖和房间连接都是稀疏图，邻接表更合适。
Unity 数据建模
推荐把编辑器配置和运行时结构分开：
- ScriptableObject 保存节点 ID、显示名称和边配置。
- 加载时验证重复 ID、悬空边和非法 Cost。
- 构建运行时邻接表。
- Jobs/Burst 热路径烘焙为
NativeArray+ 偏移表。
CSR（Compressed Sparse Row）形式能把邻居连续存储，适合大量只读图查询。
动态图的代价
频繁增加删除边时，List 会产生搬移和容量变化。可采用：
- 为每个节点预估邻居容量
- 延迟批量更新
- 使用边池和空闲列表
- 静态区与动态区分离
不要在寻路 Job 执行期间修改同一图数据。
常见坑
- 忘记有向边和无向边的区别。
- 遍历有环图时没有 visited。
- 使用浮点世界坐标作为节点身份。
- 依赖 Dictionary 遍历顺序得到确定性结果。
- A* 启发式高估真实代价，失去最优性。
- 每个敌人每帧重新构建完整图。