如何将列表的列表转为图连通分量并高效计算节点度数？

给定Python中的列表列表输入：

lst = [['1', '2'], ['1', '3', '2'], ['5'], ['4', '6']]

其中每个字符串形式的整数代表图的节点，外层列表的每个子列表表示该子列表内的所有节点两两之间存在无向边（即每个子列表是一个团）。需要计算每个节点的度数（连接的不同边的数量），重复的边需忽略，预期输出：

node_degrees = {'1': 2, '2': 2, '3': 2, '4': 1, '5': 0, '6': 1}

若直接遍历子列表并累加“子列表大小-1”到每个节点的度数，会在如下场景失效：

lst = [['1', '2'], ['2', '3'], ['3', '4'], ['4', '5']]

该场景的预期输出为：

{'1': 1, '2': 2, '3': 2, '4': 2, '5': 1}

因为直接累加会重复计算重叠团中的边，导致度数错误。需要一种低计算量的高效算法，避免暴力法的O(n²)复杂度。

方法1：维护节点的邻居集合（无重复） #

这是最直接高效的方法，核心思路是利用集合自动去重的特性，记录每个节点的所有不同邻居，最终邻居集合的大小即为度数。

实现步骤： #

1. 初始化字典，为每个节点创建空集合存储邻居。
2. 遍历每个子列表（团）：
   • 将子列表转为集合，方便快速计算当前节点的邻居。
   • 对团内每个节点，将团中除自身外的所有节点加入其邻居集合（集合自动忽略重复项）。
3. 遍历所有节点，将邻居集合的大小转为度数。

代码实现： #

def calculate_node_degrees(lst):
    neighbor_sets = {}
    
    # 初始化所有节点的邻居集合
    for sublist in lst:
        for node in sublist:
            if node not in neighbor_sets:
                neighbor_sets[node] = set()
    
    # 遍历每个团，更新邻居集合
    for sublist in lst:
        clique = set(sublist)
        for node in clique:
            # 提取当前团中除自身外的所有节点
            neighbors = clique - {node}
            neighbor_sets[node].update(neighbors)
    
    # 转换为度数字典
    return {node: len(neighbors) for node, neighbors in neighbor_sets.items()}

# 测试用例1
lst1 = [['1', '2'], ['1', '3', '2'], ['5'], ['4', '6']]
print(calculate_node_degrees(lst1))
# 输出: {'1': 2, '2': 2, '3': 2, '5': 0, '4': 1, '6': 1}

# 测试用例2
lst2 = [['1', '2'], ['2', '3'], ['3', '4'], ['4', '5']]
print(calculate_node_degrees(lst2))
# 输出: {'1': 1, '2': 2, '3': 2, '4': 2, '5': 1}

复杂度分析 #

时间复杂度为O(Σk_i)，其中k_i是每个子列表的长度。集合的update操作平均为O(1)每次元素添加，且自动去重，避免了暴力生成所有边的冗余计算，内存占用也仅为存储每个节点的邻居集合，无冗余数据结构。

方法2：并查集（仅适用于连通分量为完全图的场景） #

如果输入的子列表表示的是连通分量归属（即子列表内节点属于同一个连通分量，且分量内所有节点两两相连），可以用并查集快速合并连通分量，再通过分量大小计算度数（分量大小为1则度数0，否则为大小-1）。

代码实现： #

def calculate_node_degrees(lst):
    parent = {}
    size = {}
    
    # 查找根节点，带路径压缩
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    # 合并两个节点，按大小优化
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root == v_root:
            return
        if size[u_root] < size[v_root]:
            u_root, v_root = v_root, u_root
        parent[v_root] = u_root
        size[u_root] += size[v_root]
    
    # 初始化所有节点
    for sublist in lst:
        for node in sublist:
            if node not in parent:
                parent[node] = node
                size[node] = 1
    
    # 合并每个子列表内的节点
    for sublist in lst:
        if len(sublist) < 2:
            continue
        first = sublist[0]
        for node in sublist[1:]:
            union(first, node)
    
    # 计算度数
    return {node: size[find(node)] - 1 if size[find(node)] > 1 else 0 for node in parent}

适用场景 #

此方法仅当连通分量是完全图时有效，比如第一个测试用例。若输入是链式边集合（如第二个测试用例），则不适用，因为该方法会将所有节点合并为一个分量，计算出的度数为4（5-1），与预期不符。

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