如何递归搜索列表字典，提取所有键的全层级连通簇？

我有一个字典，每个键对应的值是该字典中其他键的列表，需要汇总所有键的全层级关联关系，形成连通簇。用循环能实现部分效果，但写不出正确的递归函数来合并所有关联列表。

输入示例 #

sampleDict = {'1': ['2', '3'],
             '2': ['1', '4'] ,
             '3': ['1'],
             '4': ['2'],
             '5': ['6'],
             '6': ['5', '7'],
             '7': ['6', '8', '9'],
             '8': ['7', '10'],
             '9': ['7', '11'],
             '10': ['8'],
             '11': ['9'],
             '12': [],
             '13': ['14'],
             '14': ['13']
             }

预期输出 #

outputDict = {1: ['1', '2', '3', '4'],
              2: ['5', '6', '7', '8', '9', '10', '11'],
              3: ['12'],
              4: ['13', '14']
              }

尝试过的代码 #

循环代码（仅合并一层关联，无法处理多层） #

for i in sampleDict.keys():
    linked = sampleDict[i]
    
    for j in linked:
        sampleDict[i] = list(set(sampleDict[i] + sampleDict[j]))

递归代码（存在死循环问题） #

def clusters(dictionary):
    for i in dictionary.keys():
        linked = dictionary[i]
        
        for j in linked:
            dictionary[i] = list(set(dictionary[i] + dictionary[j]))
            
            return clusters(dictionary)

解决方案：DFS遍历找连通簇 #

核心思路是把字典看作图（键是节点，值是相邻节点），通过标记已访问节点的方式，用深度优先搜索（DFS）找出所有连通分量，避免重复遍历和死循环。

def find_connected_clusters(graph):
    visited = set()
    clusters = []
    
    for node in graph:
        if node not in visited:
            # 用DFS遍历所有关联节点
            stack = [node]
            cluster = set()
            while stack:
                current = stack.pop()
                if current not in visited:
                    visited.add(current)
                    cluster.add(current)
                    # 添加未访问的关联节点到栈中
                    stack.extend(neighbor for neighbor in graph[current] if neighbor not in visited)
            clusters.append(sorted(cluster))  # 排序保证结果有序
    
    # 转换成要求的输出字典，键从1开始递增
    return {idx+1: cluster for idx, cluster in enumerate(clusters)}

# 测试执行
sampleDict = {'1': ['2', '3'],
             '2': ['1', '4'] ,
             '3': ['1'],
             '4': ['2'],
             '5': ['6'],
             '6': ['5', '7'],
             '7': ['6', '8', '9'],
             '8': ['7', '10'],
             '9': ['7', '11'],
             '10': ['8'],
             '11': ['9'],
             '12': [],
             '13': ['14'],
             '14': ['13']
             }

outputDict = find_connected_clusters(sampleDict)
print(outputDict)

代码说明 #

• visited集合：记录已处理的节点，彻底避免重复遍历和死循环
• DFS遍历：用栈实现深度优先搜索，逐个抓取所有关联节点，形成完整的连通簇
• 结果整理：将每个连通簇排序后，按顺序存入输出字典，键从1开始递增

原代码问题分析 #

• 循环代码：仅完成了一层关联的合并，无法递归挖掘多层关联（比如节点1关联2，2关联4，但循环无法把4加入1的列表）
• 递归代码：修改后直接递归返回，未遍历完所有节点，且没有标记已访问，会反复处理同一节点导致死循环

内容的提问来源于stack exchange，提问作者FRY-9C