图基础
图(Graph)由顶点集合 V 和边集合 E 构成,是表达对象之间多对多关系的基础结构,广泛用于社交网络、路径规划、依赖分析与推荐系统等场景。
图的分类
- 无向图(undirected):边没有方向,
(u, v)与(v, u)等价。 - 有向图(directed):边带有方向,
<u, v>表示从 u 到 v 的弧。 - 加权图(weighted):每条边附带权值,常用于表示距离、成本或时间。
- 简单图与多重图:简单图不允许自环与重边,多重图则允许。
邻接矩阵 vs 邻接表
选择存储结构需在空间与查询效率之间权衡。
| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(V²) | O(V + E) |
| 判断两顶点是否相邻 | O(1) | O(deg(v)) |
| 遍历某顶点邻居 | O(V) | O(deg(v)) |
| 适合场景 | 稠密图、频繁查询边 | 稀疏图、频繁遍历邻居 |
邻接矩阵使用 V × V 的二维数组 matrix[u][v],无权图用 0/1,加权图存权值或特殊值表示无穷。邻接表为每个顶点维护一个链表或数组,只存储实际存在的边,对稀疏图极为节省空间。
度与连通分量
在无向图中,顶点 v 的度(degree)是与其相连的边数;在有向图中分为入度(in-degree)与出度(out-degree)。连通分量指图中任意两顶点通过路径相连的最大子图;有向图对应的概念是强连通分量(SCC),可通过 Tarjan 或 Kosaraju 算法求解。
生成树与最小生成树
生成树(Spanning Tree)是包含图中全部 V 个顶点、恰好 V − 1 条边且无环的连通子图。一个连通图可有多个生成树。最小生成树(Minimum Spanning Tree, MST)是所有生成树中边权之和最小的那一棵,常用于网络布线、聚类等场景。Prim 与 Kruskal 是构造 MST 的两种经典算法,基于切分定理:对于任意切分,横切边中权值最小者一定属于某棵 MST。