Python中如何基于顶点路径和列表生成单图的边对？

首先明确问题核心：给定一个非负整数列表（代表每个顶点的度数，顶点数量等于列表长度），我们需要生成一个连通无向简单图的边对列表；若无法生成这样的图，则返回错误信息。

一、先做合法性校验（必要条件） #

在构造边之前，必须先排除不可能的情况：

• 度数总和为偶数：每条边贡献2个度数，因此所有度数的和必须是偶数，否则无法构成任何简单图。
• 无负度数：列表中不能有负数，负数度数没有实际意义。
• 最大度数限制：对于n个顶点，最大度数不能超过n-1（一个顶点最多只能连接到其他所有n-1个顶点）。
• 连通性基础条件：
  • 若n=1（单顶点）：度数必须为0，否则返回错误，此时无任何边。
  • 若n>1：不能所有度数都是0（否则是n个孤立顶点，无法连通）；同时不能存在顶点度数小于1且n>1（生成树要求每个顶点至少1度，无法满足则无法连通）。

二、最优构造方法：生成树+补边法 #

这个方法的核心是先保证连通性，再处理剩余度数，逻辑简单且易实现：

步骤1：分配度数到顶点 #

给每个顶点编号（从1到n），将输入的度数序列直接分配给对应编号的顶点（也可以先排序再分配，方便生成更接近示例的结构）。

步骤2：构造链式生成树 #

生成树是包含所有n个顶点且仅n-1条边的连通图，能保证基础连通性。我们用最简单的链式结构：连接1-2、2-3、...、n-1-n。

• 计算每个顶点的剩余度数：原始度数减去生成树中的度数（链式生成树中，两端顶点度数为1，中间顶点为2）。
• 若某个顶点剩余度数为负，说明原始度数小于生成树要求的最小度数，直接返回错误。

步骤3：处理剩余度数，添加额外边 #

剩余度数的总和一定是偶数（原始总和与生成树总和都是偶数，差值也为偶数），我们可以：

1. 收集所有剩余度数>0的顶点，用重复元素的列表简化处理（比如剩余度数为3的顶点，就在列表中添加3次该顶点）。
2. 每次从列表末尾取出两个顶点，添加一条边，同时移除这两个元素（相当于各自度数减1），直到列表为空。

步骤4：可选的连通性验证 #

虽然生成树已经保证连通，加边不会破坏连通性，但为了严谨，可通过DFS/BFS遍历所有顶点，确认所有顶点都可达。

三、Python代码实现示例 #

from collections import deque

def is_connected(n, edges):
    # BFS验证图的连通性
    adj = [[] for _ in range(n+1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    visited = [False] * (n+1)
    q = deque([1])
    visited[1] = True
    count = 1
    
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                count += 1
                q.append(v)
    
    return count == n

def build_connected_graph(degree_sequence):
    n = len(degree_sequence)
    if n == 0:
        return "错误：输入列表为空"
    
    # 合法性校验
    if any(d < 0 for d in degree_sequence):
        return "错误：存在负度数"
    total_degree = sum(degree_sequence)
    if total_degree % 2 != 0:
        return "错误：度数总和为奇数，无法构成图"
    if n == 1:
        return [] if degree_sequence[0] == 0 else "错误：单顶点度数必须为0"
    max_degree = max(degree_sequence)
    if max_degree > n-1:
        return "错误：最大度数超过顶点数-1，无法构成简单图"
    if all(d == 0 for d in degree_sequence):
        return "错误：多顶点全0度数，无法构成连通图"
    
    # 分配度数到顶点
    vertex_degrees = [(i+1, d) for i, d in enumerate(degree_sequence)]
    
    # 构造链式生成树
    edges = []
    remaining = []
    for i in range(1, n):
        u, v = i, i+1
        edges.append([u, v])
        # 更新剩余度数
        vertex_degrees[u-1] = (u, vertex_degrees[u-1][1] - 1)
        vertex_degrees[v-1] = (v, vertex_degrees[v-1][1] - 1)
    
    # 检查剩余度数合法性并收集待处理顶点
    for v, d in vertex_degrees:
        if d < 0:
            return f"错误：顶点{v}的原始度数小于生成树所需度数，无法构成连通图"
        if d > 0:
            remaining.extend([v]*d)
    
    # 处理剩余度数，添加额外边
    while len(remaining) >= 2:
        u = remaining.pop()
        v = remaining.pop()
        edges.append([u, v])
    
    # 可选：验证连通性
    if not is_connected(n, edges):
        return "错误：无法生成连通图"
    
    return edges

# 测试示例
input1 = [1,1,1,1,1,2,3,4]
print("示例1输出：", build_connected_graph(input1))

input2 = [1,1,1,2,3]
print("示例2输出：", build_connected_graph(input2))

四、生成类似示例结构的小技巧 #

如果想要生成和示例结构更接近的图，可以先将度数序列降序排序，把大度数的顶点分配到中间位置，再构造生成树，这样更容易生成星型或链式结合的结构。

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