01先把问题说具体
无向图节点 0..5,边为 0–1、1–2、3–4。一次从 0 开始的 BFS 只能访问三个点,怎样划分整张图?
02一步步得到方法
把搜索起点放进外层循环
维护 component[v],初始 −1 表示尚未分组。依次检查所有节点,若未分组,就以它为新起点做 BFS,将所有可达节点写入同一个组号。一次搜索结束后组号加 1。
孤立节点没有边,但仍然是一个连通分量,因此外层必须遍历节点全集,不能只遍历边中出现的端点。无向图中可达关系具有对称性和传递性,恰好形成互不重叠的分组。
有向图需要换定义
有向图 A→B 不说明 B 能到 A,直接套无向连通分量会依赖起点顺序。若忽略方向讨论弱连通,应先构造无向边;若要求相互可达,则是强连通分量,需要专门算法。
一次遍历只回答一个起点的可达性
从某点出发的 DFS 或 BFS 得到它所在连通块,结束后还要扫描是否有未访问节点;每遇到一个就开始新的遍历并增加分量编号,孤立点也算一个分量。
这里讨论无向图。对有向图,“忽略方向后连通”“从某点可达”和“任意两点互相可达”是不同概念,分别涉及弱连通、可达集合与强连通,不能使用同一个定义混称。
03把一个小例子完全算清楚
6 个节点,边 (0,1)、(1,2)、(3,4)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 起点 0 | 组 0 包含 {0,1,2} | 一次 BFS 标完 |
| 起点 1、2 | 跳过 | 已属于组 0 |
| 起点 3 | 组 1 包含 {3,4} | 新搜索 |
| 起点 5 | 组 2 包含 {5} | 孤立点也是一组 |
窄屏可左右滑动表格,阅读完整计算与理由。
共 3 个连通分量,标签可为 [0,0,0,1,1,2];组号本身没有大小含义。
04为什么这个方法成立
- 从一个起点搜索到且仅到其可达节点。
- 若两次搜索得到的集合有交集,则第二个起点早已被第一次标记,不会再启动,因此分组互斥。
- 遍历所有节点保证每个节点都被某次搜索覆盖。
05把推导翻译成代码
Python · 可独立运行的教学实现
from collections import deque
def components(n, edges):
adj = [[] for _ in range(n)]
for u,v in edges:
adj[u].append(v); adj[v].append(u)
labels = [-1]*n
count = 0
for start in range(n):
if labels[start] != -1:
continue
labels[start] = count
q = deque([start])
while q:
u = q.popleft()
for v in adj[u]:
if labels[v] == -1:
labels[v] = count
q.append(v)
count += 1
return labels, count逐个理解关键决定
labels[start] = count- 起点在入队前标记,孤立点也得到标签。
adj[v].append(u)- 明确构造无向图,不能少掉反向邻接。
06时间、空间与实现范围
全图中每个点入队一次,每条无向边扫描两次,时间 O(V+E),并非外层 V 次各搜索全图。
邻接表 O(V+E),标签与队列 O(V);若邻接表已给出,辅助空间 O(V)。
07改变条件,检查哪里会出错
只从 0 搜索一次就认为覆盖全图
断开的分量和孤立点会遗漏。
漏掉没有出现在边表里的孤立节点
图的节点集合应独立记录,不能只从边端点推断全部节点。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
没有边的 n 点图有几组?
需要一点提示
每个点只和自身连通。
查看解析与答案
n 组;空图 n=0 则是 0 组。
两个节点标签相同说明什么?
需要一点提示
标签来源于同次可达搜索。
查看解析与答案
在该无向静态图中存在路径相连,路径不一定是直接边。
图不断加边还要重算标签吗?
需要一点提示
之前学过动态合并。
查看解析与答案
可用并查集维护连接关系,每次加边合并两个代表,避免反复遍历整图。