解题思路
DBSCAN 基于“密度”成簇：对每个点找 eps 邻域（欧氏距离 < eps 的点集合），若邻域样本数 >min_samples，该点为核心点；从未访问的核心点出发，用 BFS/DFS 扩展，将其邻域内的点并入当前簇；若被并入的点本身也是核心点，则继续把它的邻域加入队列，直到不再扩展。最终没有被任何簇吸纳的点即为噪声点。
实现细节：
- 计算并缓存所有点的邻居列表（两两距离判断，含自身）；维度不写死，自动支持二维或三维输入。
core[i] = (len(neighbors[i]) > min_samples) 判定核心点。- 逐点扫描：若是未访问的核心点，创建新簇并用队列扩展；扩展时把邻居标成当前簇，遇到核心点则把它的邻居继续入队。
P3874.第2题-数据聚类及噪声点识别
题目内容
DBSCAN（Density−Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法。它能够识别出噪声点，发现任意形状的簇，其核心概念包括：
-
eps-邻域：样本点 P 与 点 Q 的距离小于 eps 的所有样本点的集合，即点 P 周围以 eps 为半径内所有样本点的集合。
-
核心点：若点 P 的 eps 邻域内的样本点数量大于 min_samples 的阈值，则称点 P 为核心点。
-
直接密度可达：若点 P 是核心点，且点 Q 处于点 P 的 eps 邻域内，则称点 Q 由点 P 直接密度可达。
-
密度可达：若有一串点 P1,P2,...,Pn，对于任意 i，Pi+1 可由 Pi 直接密度可达，则称点 Pn 可由点 P1 密度可达。
-
密度相连：若存在点 O ，使得点 P 和点 Q 都可由 O 密度可达，则称点 P 和点 Q 是密度相连的。
-
簇：对于任意的点 P 和点 Q ，若点 P 属于某个簇，且点 Q 由点 P 密度可达，则点 Q 也属于这个簇。同理，由点 Q 密度可达的点也属于这个簇。即同一簇内的点，是密度相连的。
-
噪声点：不属于样本集内任何簇的样本点。
请你根据以上要求实现 DBSCAN 算法，要求根据给定的数据集、eps 和 min_samples 值，输出簇的个数和噪声点的个数。
输入描述
第一行输入 3 个数 eps, min_samples, x，以空格隔开，分别表示：
- eps：计算 eps-邻域的半径值，可为小数
- min_samples：核心点的 eps-邻域内样本点数量阈值，整数
- x：数据集行数，即样本数量，整数
第二行开始为输入的样本数据，数值之间用空格隔开，共输入 x 行，每行输入数值数量为 y，2≤y≤3
输出描述
输出两个值，用空格隔开，第一个值表示得到的簇的个数，第二个值表示识别到的噪声点的个数
样例1
输入
2 2 10
0 0
3 3
6 6
9 9
12 12
2 6
6 2
9 5
5 9
10 2
输出
0 10
说明
eps 设为 2，min_samples 为 2，但给出的数据集中任意两个点之间的距离都大于2，因此即使 min_sample 设置为 2，也没有形成任何簇，即所有的点都是噪声，如下图：
样例2
输入
1 5 20
5.05 1.36
-8.19 -6.47
4.5 2.5
5.01 2.06
4.30 2.28
4.22 1.82
4.58 1.82
4.81 2.46
4.81 1.09
4.80 1.78
5.16 2.44
-6.92 -6.38
-6.84 -7.03
-6.70 -7.20
-6.83 -7.87
-6.47 -6.20
-6.70 -6.11
-6.90 -6.10
-6.99 -6.70
5 5
输出
2 2
说明
样例数据集中共 20 个点，给定 eps 为 1 ， min_samples 为 5 ，聚类后得到两个簇： 一个在坐标系第一象限，一个在第三象限，且存在两个噪声点 (5,5) 和 (−8.19,−6.47)不属于任何簇，如下图：
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
