图(Graph)

定义

图是由顶点（节点）和边组成的数据结构，用于描述对象之间的关系。边可以有方向（有向图）或无方向（无向图），也可以带权重（带权图）。

原理

图常用两种方式存储：邻接矩阵用二维数组记录任意两顶点间是否有边，适合稠密图，判断连通为 O(1) 但占用 O(V²) 空间；邻接表为每个顶点维护一个邻居列表，适合稀疏图，空间为 O(V+E)。图的基本遍历是深度优先搜索和广度优先搜索，在此之上衍生出最短路径、最小生成树、拓扑排序等众多算法。

复杂度

• 遍历（邻接表）：O(V+E)
• 邻接矩阵空间：O(V²)
• 邻接表空间：O(V+E)

应用场景

• 社交网络与好友关系
• 地图导航与路径规划
• 网页链接与搜索引擎排名
• 依赖管理与任务调度