如何根据公共端点对互相连通的线段进行分组

问题基础信息 #

现有线段列表及对应端点坐标，线段均为垂直线段，需将存在公共端点、彼此连通的线段划分为独立分组。

• 线段列表定义：

Lines = ['1', '2', '3', '4', '5', '6', '7', '8']

• 线段端点详情：

LinesDetail = {
    '1': {'I': '100', 'J': '101'},
    '2': {'I': '101', 'J': '102'},
    '3': {'I': '256', 'J': '257'},
    '4': {'I': '257', 'J': '258'},
    '5': {'I': '258', 'J': '259'},
    '6': {'I': '304', 'J': '305'},
    '7': {'I': '305', 'J': '306'},
    '8': {'I': '102', 'J': '103'}
}

• 连通关系示意图：
  
• 期望输出结果：

result = [["1","2","8"],["3","4","5"],["6","7"]]

核心思路 #

这是典型的连通分量划分问题，用并查集（DSU） 实现逻辑最简洁、运行效率最高，不需要写复杂的多层while循环遍历，核心逻辑分三步：

• 将每个线段端点视为图的节点，每条线段是连接自身I、J两个端点的边
• 通过合并操作，把所有直接、间接连通的端点归到同一个集合
• 按端点所属的连通集合，对线段做分组即可

实现代码 #

from collections import defaultdict

# 初始化并查集结构，带路径压缩优化
parent = {}
def find(x):
    parent.setdefault(x, x)
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x != root_y:
        parent[root_y] = root_x

# 第一步：合并所有线段的两个端点，标记连通关系
for line_id in Lines:
    p_i = LinesDetail[line_id]['I']
    p_j = LinesDetail[line_id]['J']
    union(p_i, p_j)

# 第二步：按连通分量对线段分组
group = defaultdict(list)
for line_id in Lines:
    # 同一条线段的两个端点必然连通，取任意一个端点的根作为分组标识即可
    root_flag = find(LinesDetail[line_id]['I'])
    group[root_flag].append(line_id)

# 整理为要求的输出格式
result = list(group.values())
print(result)
# 运行输出：[['1', '2', '8'], ['3', '4', '5'], ['6', '7']]

说明 #

• 并查集带路径压缩优化后，单次查询、合并操作的时间复杂度接近常数，哪怕线段量级达到十万级也能快速处理
• 不需要额外判断线段方向，只要两个线段共享端点就会被归到同一组，完全匹配题目中垂直线段的连通规则
• 可以直接复用该逻辑处理任意规模的同类线段连通分组需求

内容的提问来源于stack exchange，提问作者sohailnewpythonprogrammer