生成指定度序列的所有无向带权图（含自环）的算法问询

核心解决思路：递归回溯+定向剪枝 #

要枚举所有满足度序列的边组合，递归回溯是最直接的可行方案，配合针对性剪枝能避免无效分支，确保覆盖所有可能的合法图。

步骤拆解 #

1. 状态初始化

   • 用字典存储每个顶点的剩余度数，直接复用输入的度序列结构，比如remaining_deg = {v_id: deg, ...}。
   • 初始化邻接矩阵为嵌套字典，键为顶点ID，值为对应顶点的边权（初始全为0），比如adj = {u: {v:0 for v in all_vertices} for u in all_vertices}。

2. 回溯核心逻辑

   • 找到第一个剩余度数大于0的顶点u（按固定顺序遍历，比如顶点ID的字典序），作为当前处理的核心顶点。
   • 遍历所有v >= u的顶点（按ID顺序），避免重复生成无向边的对称情况（比如u-v和v-u视为同一无向边，只处理一次）：
     • 若u == v（自环）：检查剩余度数是否满足自环的度数消耗规则（比如标准无向图中自环贡献2度，需remaining_deg[u] >=2；若自定义自环贡献1度，则需remaining_deg[u] >=1）。
     • 若u != v：检查u和v的剩余度数均大于0。
   • 对每个符合条件的v，执行以下操作：
     • 添加边：更新邻接矩阵，adj[u][v] +=1，若u != v则同步更新adj[v][u] +=1（无向图对称性）。
     • 更新剩余度数：根据自环/普通边的度数规则，扣除对应度数（比如自环贡献2度则remaining_deg[u] -=2，普通边则remaining_deg[u] -=1、remaining_deg[v] -=1）。
     • 递归进入下一层：重复上述步骤，直到所有顶点剩余度数为0，此时将当前邻接矩阵复制存入结果集。
     • 回溯恢复：撤销边的添加，还原剩余度数，继续尝试下一个可能的v。

3. 关键剪枝策略

   • 对称边去重：仅处理v >= u的顶点，彻底避免无向边的重复枚举，减少一半无效分支。
   • 提前终止无效分支：若当前顶点u的剩余度数大于所有后续顶点（含自身）的剩余度数总和，直接终止该分支，因为不可能完成度数匹配。
   • 跳过无效顶点：剩余度数为0的顶点直接跳过，不做遍历。

Python实现框架示例 #

def generate_all_valid_graphs(deg_dict):
    remaining = deg_dict.copy()
    vertices = sorted(deg_dict.keys())
    adj = {u: {v: 0 for v in vertices} for u in vertices}
    results = []

    def backtrack():
        # 找到第一个有剩余度数的顶点
        current_u = next((v for v in vertices if remaining[v] > 0), None)
        if current_u is None:
            # 所有度数满足，复制邻接矩阵到结果
            results.append({u: adj[u].copy() for u in adj})
            return
        
        current_deg = remaining[current_u]
        # 遍历v >= current_u的顶点，避免重复无向边
        for v in vertices:
            if v < current_u:
                continue
            
            # 计算可添加的边数（这里按简单图处理，最多1条边；允许多重边则改为min(current_deg, remaining[v])）
            max_add = 0
            if current_u == v:
                # 自环：假设标准规则，1个自环贡献2度，最多添加current_deg//2个
                max_add = current_deg // 2
            else:
                # 普通无向边：最多添加1条（简单图）
                max_add = 1 if current_deg >=1 and remaining[v] >=1 else 0
            
            for cnt in range(1, max_add + 1):
                # 添加cnt条边
                adj[current_u][v] += cnt
                if current_u != v:
                    adj[v][current_u] += cnt
                
                # 更新剩余度数
                remaining[current_u] -= cnt * (2 if current_u == v else 1)
                if current_u != v:
                    remaining[v] -= cnt
                
                # 递归
                backtrack()
                
                # 回溯恢复
                adj[current_u][v] -= cnt
                if current_u != v:
                    adj[v][current_u] -= cnt
                remaining[current_u] += cnt * (2 if current_u == v else 1)
                if current_u != v:
                    remaining[v] += cnt
    
    backtrack()
    return results

注意事项 #

• 自环度数规则：必须明确自环对顶点度数的贡献值，这直接决定剩余度数的更新逻辑。示例中采用标准无向图规则（自环贡献2度），若自定义规则（比如自环贡献1度），需修改对应代码中的度数扣除倍数。
• 多重边支持：若带权图允许多重边，只需将max_add改为min(current_deg, remaining[v])（普通边）或current_deg（自环按1度算）即可，边权代表多重边的数量。
• 性能优化：当顶点数多或度数大时，可额外加入剪枝：比如若当前顶点的剩余度数大于后续所有顶点剩余度数之和，直接终止分支；对相同度数的顶点，可记录已处理的连接模式，避免重复分支（但题目明确度数相同的顶点为不同个体，此优化可选）。

替代思路：基于哈维尔-哈基米算法的枚举改造 #

哈维尔-哈基米算法的排序逻辑可用于优化回溯分支：

1. 每次选择剩余度数最大的顶点u，优先处理高度数顶点，更早暴露无效分支。
2. 枚举所有可能的连接组合：将u与其他顶点（含自身）连接，每次连接后更新剩余度序列，递归处理新序列。
3. 同样采用v >= u的规则避免对称边重复，结合剩余度数总和剪枝，进一步提升效率。

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