# 第 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.2 从零给出并查集的数组实现 |
| 集合（`set`）的交集运算 | 25.4.2 给出簇集合的构造与查询 |
| 欧氏距离与平方距离的等价性 | 25.5.1 给出完整证明 |
| 浮点误差与容差的取值原则 | 25.5.2 与第 26 章（工程实现纪律） |
| 单调有界数列收敛 | 25.6.2 给出离散版本（单调 + 有限取值）的证明 |
| 递归与栈深度的关系 | 25.1 给出迭代遍历写法与爆栈条件 |

## 25.1 图的表示与遍历

| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储 | `A[i][j]` 表示 `i→j` 的边权（无权重用 0/1） | `adj[i]` 存 `i` 的全部邻居 |
| 空间 | `O(V²)` | `O(V + E)` |
| 判 `(i,j)` 是否连边 | `O(1)` | `O(deg(i))`（哈希后 `O(1)`） |
| 枚举 `i` 的邻居 | `O(V)` | `O(deg(i))` |
| 适合 | 稠密图（`E ≈ V²`）、频繁随机查边 | 稀疏图（`E ≪ V²`）、只需遍历 |

**选择判据**：先估 `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` 同理改用迭代）。

| 算法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| BFS | `O(V + E)` | `O(V)` | 边权全为 1 时给出最短距离 |
| DFS（迭代） | `O(V + E)` | `O(V)` | 可求拓扑序、割点、环 |
| 并查集 | `O(E·α(V))` | `O(V)` | 只支持"合并 + 查连通"，但不必显式建图 |

## 25.2 并查集

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

```python
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
```

| 优化 | 解决的问题 | 效果 |
|---|---|---|
| 路径压缩 | 单次 `find` 沿长链爬升 | 摊还意义下把链压平 |
| 按大小合并 | `union` 时把小树挂到大树根上 | 保证树高 `O(log n)`，**即使完全不做路径压缩** |

**两种优化不能互相替代**：只做按大小合并，树高 `≤ ⌊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]]` 每轮把链长减半且无爆栈风险，**机考首选后者**。

> [!IMPORTANT]
> 并查集只回答**连通性**，**不能**回答"两点间最短距离""路径经过哪些点"；需要路径本身时必须用 BFS/DFS 或最短路算法。自检一句："题目关心的关系是否只有'是否连通'这一种？"

**应用场景与一条硬限制**：数连通块（边表 → 代表元个数）、动态连通性（在线加边 → 每次 `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`：

```
① ε-邻域：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），后果是**边界点大面积被误判为噪声点**。逐字翻译定义 ⑤："从核心点出发" ⟹ 路径上除终点外全是核心点；"相邻两者互为邻域" ⟹ 两个核心点互在邻域内则连一条无向边；"密度可达" ⟹ **在核心点诱导子图上的连通**。

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

```python
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（核心点 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，与题面"噪声点不与任何点密度相连"（**含自身**）一致。

> [!IMPORTANT]
> "记一个簇编号"与"记一个簇集合"的差别就是这道题的分差来源：前者在绝大多数数据上都对（多数点只挨着一个簇），只在**边界点被多个簇覆盖**时错。自检问法："如果某个点可以同时属于两个簇，我的数据结构能不能表示出来？"

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

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

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

> [!WARNING]
> 这类"**判据引用了尚未算完的全量信息**"的错误在多阶段模拟题中普遍存在（第 26 章会归入"口径纪律"）。通用自检：把每个判据用到的信息列出来，问"这份信息在这一步开始时是否已经完整"。

## 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`，直接比较 `≤ ε²` 会漏掉它们，故在阈值上加一个小容差。求 ε-邻域（含自身）时比较平方距离，避免开根号的误差累积：

```python
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⁻⁷` 恰在两者之间，**既吸收噪声又不会误判**。

| 容差取值 | 与噪声比（`10⁻¹⁵`） | 与最小间隙比（`10⁻⁴`，同为平方距离量纲） | 后果 |
|---|---|---|---|
| `1e−15` | 同量级 | 远小于 | 漏掉"恰好相切"的点对 |
| `1e−7` | 大 8 个量级 | 小 3 个量级 | **本题判阈值的正确选择** |
| `1e−2` | 极大 | 大于最小间隙 | 不同距离的点被判相等，邻域虚增 |
| `1e−9` | 大 6 个量级 | 小 5 个量级 | 不用于判阈值（过严）；用于判"严格更优"，见 25.6.3 |

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

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

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

| `N` | 距离矩阵规模 | 是否可行 |
|---|---|---|
| `10²` | `10⁴` | 完全可行 |
| `10³` | `10⁶` | 可行（约 8 MB） |
| `10⁴` | `10⁸` | 临界（约 800 MB，通常不可行） |
| `10⁵` | `10¹⁰` | 不可行 |

`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 的一部分）。

| 维度 | k-means | k-medoids |
|---|---|---|
| 中心位置 | 簇内均值（连续） | 必须是样本点之一（离散） |
| 挪址代价 | `O(簇大小 × 维数)` | `O(簇大小²)`（枚举候选中心） |
| 对离群点 | 敏感（均值被拉动） | 稳健（取实际点） |
| 目标函数 | 距离**平方和** | 距离**和**（本题按用户数加权） |

**挪址步骤**：对每个簇，在簇内枚举候选城市 `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 的"分簇 → 挪址"迭代在有限步内停止。

```
第一步：目标函数单调不增
  设当前配置为 (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 数），是有限数

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

> [!TIP]
> 这个证明结构可复用：**目标值单调 + 取值有限 ⟹ 有限步收敛**。k-means、EM、坐标下降都有此性质。注意结论只说收敛到**局部**最优——每次挪址只考虑单簇的局部改进。

### 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` 的取值依据是两头都要满足：

```
噪声量级：累加 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`**，否则两处同分裁决可能互相矛盾，迭代也可能在两个等价配置间来回振荡而不终止。

```python
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
```

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 图的表示选择 | 稠密或频繁查边用邻接矩阵，稀疏或只需遍历用邻接表 | 稀疏图上用 `O(V²)` 矩阵，内存溢出 |
| 距离矩阵 ≠ 邻接矩阵 | 前者全对非空、`O(N²)`；后者只记边 | 把邻域表的邻居数当距离矩阵大小 |
| 遍历实现 | 规模可能到 `10⁴` 以上就**不要用递归 DFS** | 链状图触发 `RecursionError` |
| 并查集两种优化 | 路径压缩解决单次 `find`；按大小合并保证树高 `O(log n)` | 只做一种就以为够快，或以为两者等价 |
| 迭代 `find` + 路径减半 | `parent[x] = parent[parent[x]]`，无爆栈风险 | 用递归版路径压缩，深链爆栈 |
| `α(n)` 的直观大小 | 现实规模内 `α(n) ≤ 4`，可视为常数 | 把并查集复杂度写成 `O(log n)` 并低估效率 |
| 并查集的边界 | 只回答"是否连通"，不回答距离与路径 | 用它求最短路 |
| DBSCAN 的图论翻译 | 顶点 = 核心点、边 = 核心点间邻域关系、簇 = 连通分量 | 把"核心—边界"也连边，两簇被错误连通 |
| 邻域含自身 | 计数器初值取 1 | 初值取 0，边界点大面积误判为噪声 |
| 边界点多归属 | 必须用簇集合求交集判定密度相连 | 只记一个簇编号，与另一簇的查询错判为 0 |
| 流程顺序 | 先把全部核心点定完，再标注边界点 | 边扫边判，答案随枚举顺序漂移 |
| 平方距离 | `u ≤ v ⟺ u² ≤ v²`（`u, v ≥ 0`），比较可跳过开方 | 无谓开根号，引入额外误差 |
| 阈值容差 | `1e−7`：大于浮点噪声、小于最小可分辨间隙（平方距离量纲） | 用 `1e−15`（漏判相切）或 `1e−2`（邻域虚增） |
| 严格更优容差 | `1e−9` + "严格更优才更新"实现同分取序号靠前（距离量纲） | 裸写 `<`，同分胜负由末位误差决定 |

## 自测题

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

<details><summary>答案与解析</summary>

**证明**：`u² − v² = (u − v)(u + v)`。因 `u, v ≥ 0`，故 `u + v ≥ 0`。若 `u ≤ v`，则 `u − v ≤ 0`，从而 `u² − v² ≤ 0`，即 `u² ≤ v²`；反之若 `u² ≤ v²`，即 `(u − v)(u + v) ≤ 0`，因 `u + v ≥ 0` 必有 `u − v ≤ 0`，即 `u ≤ v`。∎ **负数会让它失效**：`u = −3`、`v = 1` 时 `u ≤ v`，但 `u² = 9 > 1 = v²`，关键是 `u + v ≥ 0` 这一前提。**在 ε-邻域中的落地**：`dist(p, q) ≤ ε ⟺ (x_p − x_q)² + (y_p − y_q)² ≤ ε²`。两点注意：其一，**容差加在右侧**，写成 `squared_dist <= eps*eps + 1e-7`；加在左侧或干脆不加，都会让"距离恰好等于 ε"（题面要求"不超过"）的点对因浮点误差被漏掉。其二，**容差量级必须匹配数据精度**：`1e−7` 是针对"坐标 2 位小数"选的，若坐标有 6 位小数，平方距离最小间隙降到 `1e−12`，`1e−7` 就过大，会把不同距离的点判成相等，容差必须按数据精度重算。

</details>

**Q2**（设计）有 `N` 个点和 `N−1` 条边，判断是否构成一棵树。给出两种做法并比较。
<details><summary>答案与解析</summary>

**做法一：并查集**（不必建邻接表）——若边数不等于 `n−1` 直接判否；否则逐条 `union`，**一旦某个 `union` 返回 `False` 就说明这条边的两端已经连通，即出现环**，立即判否。**做法二：BFS/DFS**——需要先建邻接表，从任一点出发数出连通点数，等于 `n` 即为树（必须配合边数检查）。

| 维度 | 并查集 | BFS |
|---|---|---|
| 时间 | `O(N·α(N))` | `O(N)` |
| 空间 | `O(N)` | `O(N)`（邻接表） |
| 需要建邻接表 | 不需要 | 需要 |
| 能否处理多连通块 | 能（数块数） | 能（多次 BFS） |
| 能否给出路径 | **不能** | 能 |

**为什么"`n−1` 条边 + 无环"就能推出连通**：设图有 `c` 个连通分量、`n` 个顶点、`m` 条边。每个分量无环故至少是一棵树，于是 `m = Σ m_i ≤ Σ (n_i − 1) = n − c`。当 `m = n − 1` 时必有 `c = 1`。∎ **易错点**：只看 `m = n − 1` 不够（可能是"一个环 + 一个孤立点"），只看无环也不够（可能是森林），两个条件必须同时满足。

</details>

**Q3**（辨析）在 DBSCAN 中，为什么"边界点 `b` 可以同时属于两个簇"？构造一个例子，并说明只给 `b` 一个簇编号会出什么错。
<details><summary>答案与解析</summary>

**原因**：密度相连要求"存在**同一个核心点** `o` 使两点都从 `o` 密度可达"。`b` 邻域里的 `c₁`、`c₂` 分属两个连通块，于是 `b` 与两个簇都密度相连；但 `b` **不是核心点**，不能作为路径中间节点，两簇并不连通。

**具体例子**（`ε = 2.0`，`MinPts = 4`，团 A 取自 `(0,0)~(0.5,0.5)` 附近五点并令 `A5 = (0.25,0.25)`，团 B 由团 A 整体平移 `(3,0)` 得到，边界点 `b = (1.6, 0.25)`）：两团各点互相在 `ε` 内 ⟹ 都是核心点，分别同属连通块 1 与 2；`d(b, A5) = 1.35 ≤ 2.0`、`d(b, B5) = 1.65 ≤ 2.0` ⟹ `b` 在两个核心点的邻域内；但 `b` 的邻域只覆盖两团的部分点，`|N_ε(b)| < 4`，故 `b` 不是核心点。于是 `cluster_set(b) = {root(A5), root(B5)}`，含两个不同的代表元。

**只记一个簇编号（比如 1）的后果**：查询"`b` 与 `B1` 是否密度相连"时实现给出 `1 != 2`，输出 **0**，而正确答案是 1，属于静默出错；查询"`b` 与 `b`"编号相同输出 1，对边界点碰巧正确，但对噪声点仍错，所以不能靠特判 `a == b` 补救。**正确实现**是 `len(cluster_set(a) & cluster_set(b)) > 0`：`b` 与 `A1` 的交集是 `{root(A5)}`、与 `B1` 的交集是 `{root(B5)}`，都非空输出 1；噪声点与自身 `∅ ∩ ∅ = ∅` 输出 0。

</details>

**Q4**（论证）给定 `n` 个元素、初始各自成集。证明：只做"按大小合并"而不做路径压缩时，树高不超过 `⌊log₂ n⌋`。
<details><summary>答案与解析</summary>

**不变式**：对任意节点 `x`，以 `x` 为根的子树高度 `h(x) ≤ ⌊log₂ size(x)⌋`。

```
基础：叶子节点（初始状态）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)⌋
```

`rb` 及其子树上的节点高度不变，而它们所在集合变大了，不变式继续成立。**推论**：任意节点深度不超过 `⌊log₂ n⌋`，故 `find` 的代价是 `O(log n)`。**加上路径压缩为何能降到 `O(α(n))`**：路径压缩让被访问路径上所有节点的深度骤减，它解决的是"单次 `find` 沿长链爬升"，而按大小合并解决的是"`union` 把小树挂到大树上"——两者针对不同的恶化来源，效果是**相乘而非相加**：单独任一种都只到 `O(log n)` 量级，合起来才达到近乎常数的 `α(n)`。

</details>

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

**会发生什么**：设先访问 `d₂`（`best_d = 2.9999999999999996`），再访问 `d₁`，判据为假（`3.0000000000000004 > 2.9999999999999996`），保留 CDN 2；若访问顺序相反，`d₂ < best_d` 为真，也改判为 CDN 2。**结果取决于末位误差的方向而非题目规则**：换一组输入或换一种累加顺序，误差方向就会翻转，同一程序给出不一致的裁决。**正确写法**是 `if d < best_d - EPS:`（`EPS = 1e-9`）——只有"确实更近"才改判，于是"数学上相等"（实际差 `8e−16 ≪ EPS`）的两者都不触发改判，**先遍历到（序号靠前）的自然胜出**。取值依据两头都要满足：`EPS > 浮点噪声`（噪声约 `1e−15 ~ 1e−10`）、`EPS < 真实最小间隙`（坐标 2 位小数，非零距离差至少约 0.01）。**同一个 `EPS` 必须用在挪址步骤**（`cost < best_cost - EPS`），否则两处同分裁决可能矛盾，迭代也可能在两个等价配置间来回振荡而不终止。

</details>

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

```
① 求每个点的 ε-邻域（含自身）：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(集合大小)
```

**总复杂度**：`O(N² + M·k)`，`M` 为查询数、`k` 为簇集合最大大小；`N = M = 1000` 时约 `2×10⁶` 次操作，安全。**性能瓶颈**是第 ① 步的 `O(N²)` 邻域构造（`10⁶` 次距离计算）；第 ③ 步虽同为 `O(N²)`，但每条边只需一次摊还近乎 `O(1)` 的 `union`，常数极小。规模更大时改用空间网格分桶（`N ≤ 10⁵`、`ε` 很小）或近似最近邻（LSH / HNSW，放弃精确性）。**易错点回顾**：邻域必须含自身；先把核心点全定下来再处理边界点；边界点用簇集合而非单个编号；容差取 `1e−7` 而不是 `0`。

</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【2026-09-11 编程题 2】文档片段相关性判定 | 并查集 + 密度相连；边界点同属多个簇必须用簇集合求交集；平方距离 + `1e−7` 容差；迭代 `find` + 路径减半 | 25.2、25.4.1、25.4.2、25.5.1、25.5.2 |
| 【2026-08-05 编程题 1】基站空间重叠区域识别 | DBSCAN 三步分类；邻域含自身（计数器初值 1）；必须先定完全部核心点再标边界点 | 25.4.1、25.4.3 |
| 【2026-09-09 编程题 2】CDN 分发服务器选址 | k-medoids 收敛性（目标单调不增 + 配置有限）；`EPS = 1e−9` 断同分；距离按用户数加权 | 25.6.1、25.6.2、25.6.3 |
| 【2026-09-02 编程题 1】滑动窗口注意力机制 | 用掩码矩阵表示"邻接关系"，窗口截断自动完成（与邻接矩阵同构） | 25.1 |
| 【2026-09-04 编程题 1】时间序列清洗与特征评分 | 窗口统计量取自同一份快照，与"先定完核心点再标边界"同属流程顺序纪律 | 25.4.3 |
| 【2026-08-05 编程题 2】多 Agent 协作任务调度 | `p_i ≥ 1` ⟹ 状态图是 DAG ⟹ 按拓扑序单向递推 | 25.3 |

## 延伸阅读

- 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 章。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch25/  

