1. 连通图（Connected Graph）
定义：
对于一个无向图，如果任意两个点之间都至少有一条路径相连，那么这个图就是连通图。
换句话说：
-
没有孤立的点，也没有被“割断”的部分。
-
图中的所有节点都属于同一个整体。
举例：
1 -- 2
| |
3 -- 4上面这个图，1、2、3、4任意两点都可以互相到达，所以是连通图。
2. 非连通图（Disconnected Graph）
定义：
如果图中存在某些顶点对之间没有路径相连，那么这个图就叫非连通图。
举例：
1 -- 2 3 -- 4上图分成了两个“部分”，1、2无法到达3、4，显然不是连通图。
3. 连通分量（Connected Component）
定义：
在一个无向图中，每个极大连通子图称为一个连通分量。
-
“极大”的意思是不能再往里加点了，否则就不是连通的了。
-
每个分量内部是连通的，不同分量之间没有边相连。
举例：
对于这个图：
1 -- 2 3 -- 4
| |
5 6有两个连通分量：
-
第一个连通分量包含 {1,2,5}
-
第二个连通分量包含 {3,4,6}
4. 极大连通子图（Maximal Connected Subgraph）
定义：
极大连通子图就是“不能再加点了的连通子图”。
- 即每个连通分量本身就是一个极大连通子图。
理解：
其实连通分量和极大连通子图是同一个东西，只是角度不同——连通分量是全图分解后的单位，极大连通子图是强调“极大性”，不能扩展。
5. 相关扩展概念
a. 强连通图（Strongly Connected Graph, 有向图专用）
-
只用于有向图。
-
如果任意两个点 u、v，u能到v，v也能到u，则有向图强连通。
-
整个有向图强连通，则叫强连通图。
-
每个极大强连通子图叫强连通分量（SCC）。
b. 弱连通图（Weakly Connected Graph, 有向图专用）
- 有向图把所有边当成无向边后是连通的，原图叫弱连通。
6. 常见问题
-
连通分量数怎么求？
用 BFS 或 DFS，每次遇到未访问过的点就跑一遍（染色、打标记），统计总共几次，就是分量数。
-
图是连通图的判定？
从任一点出发BFS/DFS一遍，看有没有没访问到的点。
7. 代码小例子
// 求无向图连通分量数（n个点，edges存边）
vector<int> g[N];
bool vis[N];
void dfs(int u) {
vis[u] = true;
for (int v : g[u])
if (!vis[v]) dfs(v);
}
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) {
dfs(i);
cnt++; // 发现新分量
}8. 总结表格
| 概念 | 适用范围 | 含义 | 举例 |
|---|---|---|---|
| 连通图 | 无向图 | 任意两点间有路径 | 见上例（1-2-3-4） |
| 非连通图 | 无向图 | 存在至少一对点间无路径 | 见上例（1-2 与 3-4分开） |
| 连通分量 | 无向图 | 最大连通子图（互不连通） | {1,2,5} 和 {3,4,6} |
| 极大连通子图 | 无向图 | 不能再加点的连通子图 | 和连通分量等价 |
| 强连通图/SCC | 有向图 | 任意两点互可达 | 见有向图 |