第 25 章 图与集合

密度聚类在定义上是一段几何语言（邻域、核心点、密度可达），在算法上却是一道纯粹的图连通性问题。本章把这套翻译讲透：把 DBSCAN 的定义写成图，用并查集求连通分量，用平方距离加容差做比较；翻译中丢一个细节就会失分，比如"边界点可能同时属于多个簇"。

学习目标

读完本章，你应当能够：

1. 在邻接表与邻接矩阵之间按 E 与 V² 的关系做选择，并说出各自的适用边界；
2. 用 BFS 求连通分量，说明迭代与递归在栈深度、遍历次序上的差别；
3. 写出完整的并查集（parent + size、迭代 find + 路径减半），推导"按大小合并 ⟹ 树高 O(log n)"，并说明 O(α(n)) 的来源；
4. 用 Kahn 算法求拓扑序，并证明"输出长度不足 ⟺ 存在环"；
5. 把 DBSCAN 的六条定义逐条翻译成图论语言，实现"核图连通分量 + 簇集合求交集"；
6. 论证"边界点可以同时属于多个簇"，并构造出只记一个簇编号会出错的反例；
7. 用平方距离替代开根号、按数据精度选取浮点容差，并构造 O(N²) 距离矩阵；
8. 用"目标单调不增 + 配置有限"论证 k-medoids 的收敛性，并用 EPS 断同分。

前置知识检查

25.1 图的表示与遍历

选择判据：先估 E 与 V² 的关系。E 接近 V² 时矩阵更省（无指针开销）且查边更快；E ≪ V² 时必须用邻接表，否则空间爆炸。距离矩阵不是邻接矩阵：距离矩阵存"两点距离"、全对都非空（O(N²) 个值）；邻接矩阵存"是否有边"，稀疏图上绝大多数字是 0。

连通分量的标准求法是 BFS：从每个尚未归类的点出发，把它放入队列，反复弹出队首并把未访问的邻居入队，队列清空即得到一个连通分量。实现上有两处代价陷阱：弹出必须用 deque.popleft()（O(1)），写成 list.pop(0) 是 O(n)，整体会退化成 O(V²)。

迭代 DFS 与递归 DFS 有两点差异必须记住。其一是入栈顺序与递归相反：显式栈后进先出，若题目要求"与递归 DFS 完全一致的访问顺序"就要按逆序压栈。其二是同一节点会被多次压栈（压栈时不查标记），故必须在出栈时去重，否则同一节点被反复展开，最坏空间从 O(V) 涨到 O(E)。递归 DFS 在链状图上必然 RecursionError：Python 默认递归上限约 1000，而 N = 10⁵ 的链深度就是 10⁵，只要规模可能到 10⁴ 以上就不要用递归（25.2 的 find 同理改用迭代）。

25.2 并查集

并查集（disjoint set union, DSU）维护一组不相交集合，支持 find(x)（返回代表元）与 union(x, y)（合并两个集合）。parent[x] == x 表示 x 是代表元，否则沿 parent 向上找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class DSU:
    """并查集：迭代 find + 路径减半，union 用按大小合并"""
    def __init__(self, n):
        self.parent = list(range(n))       # 初始每个元素自成一个集合
        self.size = [1] * n                # 只对代表元有意义：该集合的元素个数
    def find(self, x):
        """迭代查找 + 路径减半：每步挂到祖父上，链长每轮减半；不用递归以避免深链爆栈"""
        parent = self.parent
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # 指向祖父：路径减半
            x = parent[x]
        return x
    def union(self, a, b):
        """按大小合并：把小子树挂到大树根上，树高增长最慢；返回 False 表示原本已连通"""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                # 保证 ra 是较大的那个
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

两种优化不能互相替代：只做按大小合并，树高 ≤ ⌊log₂ n⌋、find 是 O(log n)；只做路径压缩，单次 find 仍可能慢，摊还接近 O(1)；两者结合才达到 O(α(n))，α 是反阿克曼函数（inverse Ackermann function）。α(n) 的现实大小是 α(10⁵) ≈ 3、α(10⁹) ≈ 4，一切现实规模下 α(n) ≤ 4，可视为常数：所以"O(N²) 建边 + 并查集"整体写作 O(N² + N·α(N)) 而不是 O(N² log N)。路径减半 vs 完整路径压缩：递归写法 p[x] = find(p[x]) 一次把整条链压平但有爆栈风险；迭代写法 p[x] = p[p[x]] 每轮把链长减半且无爆栈风险，机考首选后者。

应用场景与一条硬限制：数连通块（边表 → 代表元个数）、动态连通性（在线加边 → 每次 union 后的块数）、等价类划分（等价对 → 每个元素的代表元）、DBSCAN 核心点分簇（互在邻域内的核心点对 → 每个核心点的簇编号）、Kruskal 最小生成树（按边权排序的边 → 每次合并是否成功）。并查集不支持删边；要求动态断边时须离线倒序处理（把删除转成加入）或改用 Link-Cut Tree。

25.3 拓扑排序

Kahn 算法的流程是：统计每个点的入度，把入度为 0 的点入队；每次出队一个点接到拓扑序末尾，并把它的后继入度减一；某个后继入度归零时说明它的全部前驱都已排好，可以入队。若最终输出的点数不足 n，则图中有环。“输出长度不足 ⟺ 存在环"的证明思路：DAG 中必存在入度为 0 的节点，删掉它对入度的贡献后剩余图仍是 DAG，归纳可知所有节点都会被输出；反之若存在环，环上每个节点在环内的入度至少为 1，它永远等不到入度归零，故输出长度小于 n。两个方向合起来即为等价。

在本书中的位置：拓扑排序用于理解依赖关系的处理顺序（第 19 章计算图调度、第 21 章流水线微批顺序）。它与第 24.4.2 节的"单调量严格变化 ⟹ DAG ⟹ 单向递推"是同源的——单调量的严格变化关系本身就是一张 DAG，按该量升序处理即得到拓扑序；若出现自环或环，就必须改用最短路，或先做强连通分量缩点。

25.4 密度聚类与连通分量

25.4.1 DBSCAN 的六条定义与图论翻译

给定点集 D、邻域半径 ε、最小点数 MinPts：

1
2
3
4
5
6
7

① ε-邻域：N_ε(p) = { q ∈ D : dist(p, q) ≤ ε }        （含 p 自身）
② 核心点：|N_ε(p)| ≥ MinPts
③ 边界点：p 不是核心点，但存在核心点 q 使 p ∈ N_ε(q)
④ 噪声点：既非核心也非边界
⑤ 密度可达：从核心点 p 出发，经一串核心点 q₁, q₂, …, q_k 到达 r，
             且相邻两者互为邻域（q_i ∈ N_ε(q_{i+1})）
⑥ 密度相连：存在核心点 o，使 p 与 q 都从 o 密度可达

邻域包含自身这条极易被漏掉：漏掉之后每个点的邻域计数都少 1（计数器初值从 1 变成 0），后果是边界点大面积被误判为噪声点。逐字翻译定义 ⑤：“从核心点出发” ⟹ 路径上除终点外全是核心点；“相邻两者互为邻域” ⟹ 两个核心点互在邻域内则连一条无向边；“密度可达” ⟹ 在核心点诱导子图上的连通。

1
2

构造图 G：顶点 = 全部核心点；边 = 所有满足 q ∈ N_ε(p) 的核心点对 (p, q)
核心点 p 的簇 = p 在 G 中的连通分量；两个核心点同簇 ⟺ 在 G 中连通 ⟺ 密度可达

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def core_components(n, neighbors, is_core):
    """把互在邻域内的核心点合并。neighbors[i] 是 i 的 ε-邻域（含自身）。"""
    dsu = DSU(n)
    for i in range(n):
        if not is_core[i]:
            continue                       # 非核心点不能向外迈步
        for j in neighbors[i]:
            if is_core[j]:                 # 两端都是核心点才连边
                dsu.union(i, j)
    return dsu

为什么只连"核心—核心"边：边代表"一步密度可达”，而定义要求每一步都从核心点出发，所以非核心点不能作为路径的中间节点；若把"核心—边界"也连边，两个本该分开的簇就会通过一个边界点连通，这正是下一小节的坑。

25.4.2 边界点的多簇归属：本章第一号失分点

设边界点 b 的邻域里有两个来自不同簇的核心点 c₁、c₂：

1
2
3
4
5
6

   簇 1（核心点 c₁ 所在连通块）        簇 2（核心点 c₂ 所在连通块）
      ●───●───●                              ●───●
           ╲                                    ╱
            ● b（边界点，不是核心点）
           ╱                                    ╲
      ●───●                                      ●───●

b 与簇 1 的点密度相连（共同核心点 c₁），也与簇 2 的点密度相连（共同核心点 c₂），但簇 1 与簇 2 并不连通：b 不是核心点，不能作为路径的中间节点。因此 b 同时属于两个簇，必须给每个点记一个簇集合而不是一个编号：cluster_set(i) 在 i 是核心点时取 { find(i) }，在 i 是边界点时取 { find(j) : j ∈ N_ε(i) 且 j 是核心点 }（可含多个代表元），在 i 是噪声点时取 ∅；查询 a 与 b 密度相连 ⟺ cluster_set(a) ∩ cluster_set(b) ≠ ∅。为什么用交集：交集非空意味着存在同一个核心点 o，使 a 与 b 都从 o 密度可达——这正是"密度相连"的定义，而"代表元相同"只捕捉了"属于同一连通块"这一更弱的信息，对边界点不成立。噪声点的自洽性：a == b 且 a 是噪声点时 cluster_set(a) = ∅，交集为空输出 0，与题面"噪声点不与任何点密度相连"（含自身）一致。

1
2
3
4
5
6
7
8
9

def build_cluster_sets(n, neighbors, is_core, dsu):
    """核心点只属于自己所在簇；边界点挂在覆盖它的全部核心点所在簇上；噪声点为空集。"""
    return [{dsu.find(i)} if is_core[i]
            else {dsu.find(j) for j in neighbors[i] if is_core[j]}
            for i in range(n)]

def density_connected(sets, a, b):
    """密度相连 ⟺ 簇集合有交集（存在同一个核心点能走到两者）"""
    return len(sets[a] & sets[b]) > 0

25.4.3 三步分类流程

【2026-08-05 编程题 1】只要求分类而不要簇标签，流程更短，但顺序纪律相同：

1
2
3

第 1 步：统计每个点的邻域规模（含自身，故计数器初值取 1）
第 2 步：把全部核心点确定下来 —— 判据 Count_i ≥ MinPts 只依赖自己
第 3 步：标注属性 —— 核心点标 0；非核心点邻域内有核心点则标 1，否则标 2

为什么第 2 步必须完整跑完才能进第 3 步：边界点的判据是"邻域内至少有一个核心点"，它引用的是最终的核心点集合；若边扫边判，下标靠前的点在判定时看不到后面尚未确定的核心点，同一组输入就会因枚举顺序不同得出不同答案。

1
2
3
4

反例：点 0 不是核心点，点 1 是核心点，且 dist(0,1) ≤ ε
  顺序 A（0 先）：判定点 0 时只知"前面没有核心点" ⟹ 标 2（错）
  顺序 B（1 先）：判定点 0 时看到点 1 是核心点   ⟹ 标 1（对）
真相：点 0 是边界点，应为 1 —— 顺序 A 给出了错误却"看起来合理"的答案

25.5 距离计算与浮点容差

25.5.1 用平方距离代替开根号

欧氏距离 d = √((x₁−x₂)² + (y₁−y₂)²) 需要开方，而开方既慢（一次 sqrt 约抵几次乘加）又引入舍入误差，在只需比较距离大小的场合可以完全跳过。命题：对非负实数 u, v，有 u ≤ v ⟺ u² ≤ v²。证明：u² − v² = (u − v)(u + v)；因 u, v ≥ 0 故 u + v ≥ 0，于是 u² − v² 与 u − v 同号（且同时为零）。∎ 命题给出的是等价而非单向蕴含，故 ≤ 与 < 的严格性都保留：dist(p, q) ≤ ε ⟺ (x₁−x₂)² + (y₁−y₂)² ≤ ε²。前提 u + v ≥ 0 不可省：取 u = −3、v = 1，有 u ≤ v 但 u² = 9 > 1 = v²，命题失效。

25.5.2 容差的取值原则

浮点运算不精确，dist = ε 的点对可能算成 ε + 1e−16，直接比较 ≤ ε² 会漏掉它们，故在阈值上加一个小容差。求 ε-邻域（含自身）时比较平方距离，避免开根号的误差累积：

1
2
3
4
5
6

lim = eps * eps + 1e-7                  # 容差须大于浮点噪声、又远小于真实可分辨间隙
neighbors = []
for i in range(n):
    xi, yi = xs[i], ys[i]
    neighbors.append([j for j in range(n)
                      if (xs[j] - xi) ** 2 + (ys[j] - yi) ** 2 <= lim])

两条约束方向相反，容差必须落在中间：EPS 必须大于累加噪声量级，否则"数学上相等"的点对被判为不等；又必须小于真实可分辨的最小间隙，否则"数学上不等"的点对被判为相等。【2026-09-11 编程题 2】的参数下，坐标最多 2 位小数，平方距离最小非零间隙是 10⁻⁴（如 (0.01)²），浮点累加噪声约 10⁻¹⁵；取 10⁻⁷ 恰在两者之间，既吸收噪声又不会误判。

同一题里可能同时需要两种尺度的容差：判"是否落在阈值内"用较大容差 1e−7（要吸收"相等"的误差），判"严格更优"用较小容差 1e−9（只需区分"确实更好"与末位噪声）。混用会出问题。

25.5.3 距离矩阵的 O(N²) 构造

点对会被反复访问时（如 k-medoids 的迭代），把距离预计算成矩阵：只算上三角一半，再利用 d[i][j] = d[j][i] 对称填充两处，时间与空间都比全枚举省一半。

N = 10⁵ 时既不能建距离矩阵也不能建邻域表，只能退化为"对每个点扫一遍全部点"的 O(N²) 时间 + O(N) 空间。

25.6 迭代聚类的收敛性：以 k-medoids 为例

25.6.1 与 k-means 的关键差别

【2026-09-09 编程题 2】要求"CDN 选址必须在城市内"。k-means 的簇心取簇内坐标均值，可落在任意位置；本限制使得挪址时只能从簇内已有城市中挑一个——这就是 k-medoids（PAM 的一部分）。

挪址步骤：对每个簇，在簇内枚举候选城市 c，使加权代价 cost(cluster, c) = Σ_{i ∈ cluster} u_i · d(city_i, city_c) 最小者成为新中心。题目目标是 Σ_i u_i · d(city_i, 最近的 CDN)，用户数 u_i 是权重，必须按用户数加权：漏掉权重会选出错误的中心，因为大用户量城市对中心的拉力更大。

25.6.2 收敛性证明

定理：k-medoids 的"分簇 → 挪址"迭代在有限步内停止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

第一步：目标函数单调不增
  设当前配置为 (C_t, assignment_t)，总代价 J_t = Σ_i u_i · d(city_i, center(i))
  ● 分簇步：固定中心 C_t，把每个点归给最近的 CDN
      每个点独立选择最近中心 ⟹ 这是"给定中心下的最优分配" ⟹ 新的 J' ≤ J_t
  ● 挪址步：固定分簇，为每个簇选最优中心
      各簇目标是 Σ_{i∈cluster} u_i · d(city_i, c)，簇间互不影响，
      故逐簇取最优即全局最优 ⟹ 新的 J'' ≤ J'
  合起来：J_{t+1} ≤ J_t，即总代价单调不增

第二步：状态空间有限
  每个 CDN 必须建在城市里 ⟹ 每个中心有 p 种取值（p 为城市数）
  ⟹ 全部配置数为 p^q（q 为 CDN 数），是有限数

两步合并：
  总代价单调不增，且取值来自有限集合
  ⟹ 不可能无限次严格下降（每次严格下降都要换到一个代价更小的配置，
     而这样的配置只有有限多个）
  ⟹ 迭代必在有限步内停止。实现上用"新旧中心完全一致就停止"来排除同代价配置间的循环。

25.6.3 用 EPS 断同分

“严格更优才更新"是实现"同分取序号靠前"的标准手法：分簇时写 if d < best_d - EPS（等距时不动，序号小的自然胜出）；挪址时写 if best_c < 0 or cost < best_cost - EPS（代价相等时不动，城市序号小的自然胜出）。不能裸写 cost < best_cost：样例里"选城市 0"与"选城市 1"的代价数学上相等，浮点算出来却差约 1e−15，用裸的 < 时谁赢取决于末位误差，题目规则就失控了。EPS = 1e−9 的取值依据是两头都要满足：

1
2
3
4

噪声量级：累加 p 个浮点数，误差约 p · 2⁻⁵² · 数量级 ≈ 10⁻¹⁵ ~ 10⁻¹⁰
真实间隙：两座不同城市的距离差至少约 0.01（坐标 2 位小数，量纲为"距离"本身）
取 EPS = 1e−9：比噪声大 3~6 个量级   ⟹ 同类代价不会被误判为"更优"
              比真实间隙小 7 个量级   ⟹ 真实更优不会被误判为"同分"

注意量纲：这里的间隙是距离本身（0.01），而 25.5.2 节的间隙是平方距离（10⁻⁴）。两者不能直接比较——1e−9 相对 0.01 小 7 个量级，相对平方距离的 10⁻⁴ 只小 5 个量级。判据所在的量纲决定了"小几个量级"的说法，写题解时必须声明。

分簇与挪址必须用同一个 EPS，否则两处同分裁决可能互相矛盾，迭代也可能在两个等价配置间来回振荡而不终止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from math import sqrt

EPS = 1e-9          # 判"严格更优"的容差：须大于浮点噪声、小于真实代价间隙

def city_dist(a, b):
    """两座城市的欧氏距离；a、b 为 (x, y, u) 三元组"""
    return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
def assign(cs, centers):
    """分簇：每个城市归给最近的 CDN，等距时保留序号靠前者"""
    cluster = [[] for _ in centers]
    for i in range(len(cs)):
        best_j, best_d = 0, city_dist(cs[i], cs[centers[0]])
        for j in range(1, len(centers)):
            d = city_dist(cs[i], cs[centers[j]])
            if d < best_d - EPS:           # 只有"确实更近"才改判
                best_d, best_j = d, j
        cluster[best_j].append(i)
    return cluster
def relocate(cs, centers, cluster):
    """挪址：簇内换一个城市当 CDN，使簇内加权距离和最小"""
    nxt = list(centers)
    for j, mem in enumerate(cluster):
        if not mem:
            continue                       # 空簇没有候选城市，保持原址
        best_c, best_cost = -1, 0.0
        for c in mem:
            cost = sum(cs[i][2] * city_dist(cs[i], cs[c]) for i in mem)  # 按用户数加权，不能漏
            if best_c < 0 or cost < best_cost - EPS:
                best_cost, best_c = cost, c
        nxt[j] = best_c
    return nxt
def solve(cs, q):
    """迭代到 CDN 不再变化：目标单调不增 + 配置有限 ⟹ 必收敛"""
    centers, cluster = list(range(q)), [[] for _ in range(q)]   # 初始 CDN 为前 q 个城市
    for _ in range(1000):                  # 上限仅兜底，实际几轮就收敛
        cluster = assign(cs, centers)
        nxt = relocate(cs, centers, cluster)
        if nxt == centers:                 # 中心不变即停止
            break
        centers = nxt
    return centers, cluster

本章小结

自测题

Q1（论证）证明：对非负实数 u, v，u ≤ v ⟺ u² ≤ v²。负数会让它失效吗？在求 ε-邻域时用平方比较还要注意什么？

Q2（设计）有 N 个点和 N−1 条边，判断是否构成一棵树。给出两种做法并比较。

Q3（辨析）在 DBSCAN 中，为什么"边界点 b 可以同时属于两个簇"？构造一个例子，并说明只给 b 一个簇编号会出什么错。

Q4（论证）给定 n 个元素、初始各自成集。证明：只做"按大小合并"而不做路径压缩时，树高不超过 ⌊log₂ n⌋。

1
2
3
4
5
6
7
8
9

基础：叶子节点（初始状态）size = 1，h = 0 = ⌊log₂ 1⌋

归纳步：设把根 rb 挂到根 ra 上，按大小合并保证 size(rb) ≤ size(ra)
  size_new(ra) = size(ra) + size(rb) ≥ 2 · size(rb)
  新树高 h_new(ra) = max(h(ra), h(rb) + 1)
    由归纳假设 h(ra) ≤ ⌊log₂ size(ra)⌋ ≤ ⌊log₂ size_new(ra)⌋
                h(rb) ≤ ⌊log₂ size(rb)⌋ ≤ ⌊log₂(size_new(ra)/2)⌋ = ⌊log₂ size_new(ra)⌋ − 1
                ⟹ h(rb) + 1 ≤ ⌊log₂ size_new(ra)⌋
    故 h_new(ra) ≤ ⌊log₂ size_new(ra)⌋

Q5（设计）k-medoids 分簇时两个 CDN 与某城市距离数学上相等，浮点算出 d₁ = 3.0000000000000004、d₂ = 2.9999999999999996。写成 if d < best_d: 会发生什么？该怎么改？

Q6（综合）输入含 N ≤ 1000 个二维点，需回答若干查询点对是否"密度相连"（ε、MinPts 给定）。写出完整算法流程与复杂度，并指出性能瓶颈。

1
2
3
4
5
6
7

① 求每个点的 ε-邻域（含自身）：O(N²)
   - 比较平方距离 + 容差 1e−7；结果存成邻域表（最坏 O(N²) 空间）
② 判定核心点：is_core[i] = (len(neighbors[i]) >= MinPts)：O(N)
③ 核心点建边并用并查集合并：O(N²·α(N))（只合并"互在邻域内的核心点对"）
④ 构造每个点的簇集合：O(N²)
   - 核心点 {find(i)}；边界点 {find(j) : j ∈ neighbors[i] 且 j 是核心点}；噪声点 ∅
⑤ 回答每个查询：对两个簇集合求交集，O(集合大小)

与真题的关联

延伸阅读

• Cormen, Leiserson, Rivest, Stein，《Introduction to Algorithms》第 21 章"用于不相交集合的数据结构"——O(α(n)) 界的完整证明与势能分析。
• Tarjan, R. E., “Efficiency of a Good But Not Linear Set Union Algorithm”（JACM, 1975）——并查集复杂度的奠基论文。
• Ester, Kriegel, Sander, Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”（KDD-96）——DBSCAN 原始论文，核心点/边界点/噪声的定义出处；k-medoids 的标准参考见 Kaufman & Rousseeuw《Finding Groups in Data》第 2 章。