如何为同属一个网络的字典分配相同ID

给定如下列表：

my_dict = [{'s':1,'t':2},
    {'s':2,'t':3},
    {'s':3,'t':1},
    {'s':4,'t':5},
    {'s':5,'t':6},
    {'s':6,'t':4}]

需要将其转换为：

output = [{'s':1,'t':2,'id':1},
    {'s':2,'t':3,'id':1},
    {'s':3,'t':1,'id':1},
    {'s':4,'t':5,'id':2},
    {'s':5,'t':6,'id':2},
    {'s':6,'t':4,'id':2}]

说明：前3个字典属于同一个连通网络，后3个属于另一个，因此为同一网络内的字典分配相同的id。

核心是识别每条边所属的连通分量，再为每个分量分配唯一ID，用BFS遍历实现：

def assign_network_ids(edges):
    # 构建图的邻接表
    graph = {}
    for edge in edges:
        s, t = edge['s'], edge['t']
        graph.setdefault(s, []).append(t)
        graph.setdefault(t, []).append(s)
    
    # 记录节点对应的分量ID
    node_id_map = {}
    current_id = 1
    
    # 遍历所有节点，标记连通分量
    for node in graph:
        if node not in node_id_map:
            queue = [node]
            node_id_map[node] = current_id
            while queue:
                curr_node = queue.pop(0)
                for neighbor in graph[curr_node]:
                    if neighbor not in node_id_map:
                        node_id_map[neighbor] = current_id
                        queue.append(neighbor)
            current_id += 1
    
    # 为每条边添加对应ID
    result = []
    for edge in edges:
        new_edge = edge.copy()
        new_edge['id'] = node_id_map[edge['s']]
        result.append(new_edge)
    
    return result

# 测试执行
my_dict = [{'s':1,'t':2},
    {'s':2,'t':3},
    {'s':3,'t':1},
    {'s':4,'t':5},
    {'s':5,'t':6},
    {'s':6,'t':4}]

output = assign_network_ids(my_dict)
for item in output:
    print(item)

代码说明 #

1. 邻接表构建：把所有边转换为图的邻接表结构，方便后续遍历节点关系。
2. 连通分量标记：用BFS遍历未标记的节点，将同一连通分量内的所有节点绑定到同一个ID。
3. ID分配：遍历原始边列表，为每条边添加其所属连通分量的ID。

运行代码后即可得到目标输出。

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