专题进阶 · 图算法推荐总顺序 · 第 55 / 148 课

从一次可达搜索扩展为整图分组,正确计入孤立节点。

还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

连通分量Connected Components

每次从未访问节点启动 DFS/BFS,能划分无向图的连通块。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

从一次可达搜索扩展为整图分组,正确计入孤立节点。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 从一个起点搜索到且仅到其可达节点。
  2. 若两次搜索得到的集合有交集,则第二个起点早已被第一次标记,不会再启动,因此分组互斥。
  3. 遍历所有节点保证每个节点都被某次搜索覆盖。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

没有边的 n 点图有几组?

需要一点提示

每个点只和自身连通。

查看解析与答案

n 组;空图 n=0 则是 0 组。

练习 2 · 边界与辨析

两个节点标签相同说明什么?

需要一点提示

标签来源于同次可达搜索。

查看解析与答案

在该无向静态图中存在路径相连,路径不一定是直接边。

练习 3 · 变式与迁移

图不断加边还要重算标签吗?

需要一点提示

之前学过动态合并。

查看解析与答案

可用并查集维护连接关系,每次加边合并两个代表,避免反复遍历整图。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。