图

图是由顶点和边组成的数据结构，用来表示多对多关系。

常见场景：

• 社交关系；
• 地图路径；
• 网络拓扑；
• 任务依赖；
• 推荐关系。

一、基本概念

概念	说明
顶点	图中的节点
边	顶点之间的连接
有向图	边有方向
无向图	边没有方向
权重	边上的代价或距离
度	与某顶点相连的边数量

二、存储方式

邻接矩阵

使用二维数组表示顶点之间是否相连。

优点：

• 判断两个点是否相连很快；
• 实现简单。

缺点：

• 空间复杂度 O(n²)；
• 稀疏图浪费空间。

邻接表

每个顶点维护一个相邻顶点列表。

优点：

• 适合稀疏图；
• 空间更节省。

缺点：

• 判断两点是否相连需要遍历列表。

三、图遍历

深度优先搜索 DFS

适合：

• 连通性判断；
• 路径搜索；
• 拓扑相关问题。

广度优先搜索 BFS

适合：

• 最短路径；
• 层级遍历；
• 扩散类问题。

四、常见算法

• 最短路径：Dijkstra、Floyd。
• 最小生成树：Prim、Kruskal。
• 拓扑排序：解决依赖顺序。
• 连通分量：判断图的连通区域。

五、练习

• 用邻接矩阵表示图。
• 用邻接表表示图。
• 实现 DFS。
• 实现 BFS。
• 判断两个顶点是否连通。