本文介绍如何利用深度优先搜索（dfs）将具有传递相似关系的元素自动聚类为连通分量，并输出以短横线连接的字符串形式的簇，适用于无向图建模的相似性分组任务。
本文介绍如何利用深度优先搜索（dfs）将具有传递相似关系的元素自动聚类为连通分量，并输出以短横线连接的字符串形式的簇，适用于无向图建模的相似性分组任务。
在数据分析和特征工程中，常遇到“相似性传递”问题：若 (a, b) 和 (b, c) 同时存在，则 a、b、c 应归属同一组——这本质上是无向图的连通分量（Connected Components）识别问题。给定配对列表，我们可将其视为边集，构建邻接表表示的图，再通过 DFS 或 BFS 遍历每个未访问节点，找出所有极大连通子图。
以下是一个健壮、可读性强且无需第三方图库的纯 Python 实现（兼容 Python 3.6+）：
from collections import defaultdict, deque
def cluster_by_similarity(pairs):
# 构建无向图邻接表（使用 defaultdict 自动初始化空列表）
graph = defaultdict(list)
for a, b in pairs:
graph[a].append(b)
graph[b].append(a)
visited = set()
clusters = []
# 对每个未访问节点启动 DFS
def dfs(start):
stack = [start]
component = []
visited.add(start)
while stack:
node = stack.pop()
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
return component
# 遍历所有可能出现的节点（覆盖孤立点，尽管本例中无）
all_nodes = set(graph.keys())
for node in all_nodes:
if node not in visited:
cluster = dfs(node)
clusters.append(cluster)
# 按字典序排序各簇内元素（可选，提升结果一致性），再拼接为字符串
return ['-'.join(sorted(c)) for c in clusters]
# 示例输入
col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'),
('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'),
('j','k')]
# 执行聚类
result = cluster_by_similarity(col_combi)
print(result)
# 输出：['a-b-c-g', 'd-e-m-p-z', 'j-k-l-n-t']
✅ 关键说明与注意事项：
-
图的无向性：每对
(x, y)被双向添加到邻接表，确保x可达y，y也可达x； -
鲁棒性增强：使用
defaultdict(list)替代手动键检查，避免KeyError；显式收集all_nodes确保不遗漏任何顶点（即使某节点仅作为邻居出现）； -
排序建议：
sorted(c)使输出顺序稳定（如'a-b-c-g'而非'b-a-g-c'），便于测试与比对；若需保持原始出现顺序，可改用list(dict.fromkeys(...))去重保序； -
替代方案：若项目已引入
networkx，一行即可解决：import networkx as nx G = nx.Graph(col_combi) result = ['-'.join(sorted(c)) for c in nx.connected_components(G)]
- 时间复杂度：O(V + E)，其中 V 为唯一节点数，E 为配对数，高效适用于万级规模数据。
该方法逻辑清晰、易于调试，是处理关系型分组任务的经典范式。掌握其原理，可轻松迁移至并查集（Union-Find）等更高效的大规模场景。
