图的连通性
知识总结
连通性概念
- 连通：无向图中，两个顶点之间存在路径
- 连通图：任意两个顶点都连通的无向图
- 连通分量：无向图中的极大连通子图
- 强连通：有向图中，u到v和v到u都有路径
- 强连通图：任意两个顶点都强连通的有向图
树与图的关系
- 树是一种特殊的图：连通且无环
- n个顶点的树恰好有 n-1 条边
- 在树中添加一条边必然产生环
- 在树中删除一条边必然不连通
生成树
- 连通图的生成树：包含所有顶点的极小连通子图
- n个顶点的连通图的生成树有 n-1 条边
- 最小生成树（MST）：所有生成树中边权之和最小的
最小生成树算法
| 算法 | 思想 | 时间复杂度 |
|---|---|---|
| Kruskal | 按边权排序，贪心选边 | O(m log m) |
| Prim | 从一个点出发，逐步扩展 | O(n²) 或 O(m log n) |
初赛常考
- 判断图是否连通
- 求连通分量个数
- n个顶点至少需要多少条边才能连通（答案：n-1）
- 生成树的边数