| 项目 | 值 |
|---|---|
| 主题 | 图的连通性判断 |
| 核心方法 | 方法一：DFS / BFS；方法二：邻接矩阵的幂 |
| 时间复杂度 | 暴力判强连通 $O(n(n+e))$ |
| 难度 | ⭐⭐⭐ |
| 条件 | 说明 |
|---|---|
| $n$ 个顶点的连通图最少边数 | $n-1$（树） |
| $n$ 个顶点的非连通图最少边数 | 0 |
| $n$ 个顶点的连通图最多边数 | $n(n-1)/2$（完全图） |
| $n$ 个顶点的非连通图最多边数 | $(n-1)(n-2)/2$（一个孤立点 + 完全图） |
从任意一个顶点出发做 DFS 或 BFS：
统计连通分量个数：
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
DFS(G, i);
count++; // 每次调用 DFS 发现一个新的连通分量
}
}
// count 就是连通分量的个数
// count == 1 表示连通图对每个顶点做 DFS，检查是否能到达所有其他顶点。时间复杂度 $O(n(n+e))$。
利用 DFS 树和栈，在一次 DFS 中找出所有强连通分量。核心概念：
dfn[u] == low[u] 时，$u$ 是强连通分量的根题目：无向图有 5 个顶点，邻接矩阵如下，判断是否连通。
A B C D E
A [ 0 1 1 0 0 ]
B [ 1 0 0 1 0 ]
C [ 1 0 0 0 0 ]
D [ 0 1 0 0 0 ]
E [ 0 0 0 0 0 ]分析：从 A 出发 DFS：A → B → D → C（访问了 4 个顶点）。E 没有被访问到，所以不连通。
连通分量：$\{A, B, C, D\}$ 和 $\{E\}$，共 2 个连通分量。
题目：无向图如下，求连通分量个数。
1 — 2 4 — 5
| |
3 6 — 7
8分析：
连通分量个数：3
题目：有向图如下，判断是否强连通，求强连通分量。
A → B → C → A
↓
D → E → D分析：
题目：6 个顶点的非连通无向图最多有多少条边？
分析：非连通图最多边数 = 一个孤立点 + 其余 $n-1$ 个点构成完全图。
$$E_{max} = \binom{n-1}{2} = \binom{5}{2} = 10$$
| 性质 | 值 |
|---|---|
| $n$ 顶点连通图最少边 | $n-1$ |
| $n$ 顶点非连通图最多边 | $(n-1)(n-2)/2$ |
| 无向图连通性判断 | DFS/BFS 一次遍历是否访问所有顶点 |
| 连通分量个数 | DFS 调用次数 |
| 生成树边数 | $n-1$（$n$ 为连通图顶点数） |
dfn[u] == low[u] 时 $u$ 是该强连通分量的根。（暂无关联知识点）
↑ 本页右上「在 Obsidian 中打开」可跳回源笔记。