有向图双边修改生成器实现：递归方案优化及问题排查

我用二维列表表示有向图的邻接矩阵，边权重仅为1或2，0表示无有向边，矩阵的每个子列表对应节点的出边。需求是生成所有双边修改后的图（即对两条不同的非自环边进行修改，每条边改为原权重之外的可能值），用于测试。

示例邻接矩阵：

nodes = ["1", "2", "3", "4", "5"]
edges = [
  [0, 2, 1, 2, 0],
  [1, 0, 1, 0, 0],
  [0, 2, 0, 0, 0],
  [1, 0, 1, 0, 2],
  [1, 2, 0, 0, 0],
]

比如修改后的示例（添加节点"4"到"5"权重为1的边，并移除节点"1"到"4"权重为1的边）：

edges = [
  [0, 2, 1, 2, 0],
  [1, 0, 1, 0, 0],
  [0, 2, 0, 0, 0],
  [0, 0, 1, 0, 2],
  [1, 2, 0, 1, 0],
]

最初递归代码的问题 #

我写了一段递归代码试图实现需求，但没有输出：

def all_modification_generation(graph: list[list], iter_count: int = 0):
    possible_weights = {-1, 0, 1}
    node_len = len(graph)
    for i in range(node_len**2):
          ix_x = i // node_len
          ix_y = i % node_len
          if i == ix_y:  # 自环判断逻辑错误
              continue
          for possible_pertubs in possible_weights - {graph[ix_x][ix_y]}:
              graph[ix_x][ix_y] = possible_pertubs
              if iter_count == 0:
                  all_modification_generation(graph=graph, iter_count=iter_count + 1)
              else:
                  yield all_modification_generation(graph=graph)

问题出在这几点：

1. 自环判断错误：用i == ix_y替代了正确的ix_x == ix_y，导致大量自环未被跳过。
2. 原对象被修改：递归中直接修改传入的图，没有深拷贝，会污染后续递归的状态。
3. 生成器使用错误：yield all_modification_generation(...)返回的是生成器对象而非修改后的图；递归调用时没有用yield from展开结果。
4. 逻辑漏洞：首次递归调用未收集结果，第二次迭代返回的是生成器而非最终修改后的图。

可行但冗余的循环实现 #

后来我写出了能运行的代码，但存在代码重复和四层嵌套循环的问题：

from copy import deepcopy

def all_modification_generation(graph: list[list]):
    possible_weights = {-1, 0, 1}
    node_len = len(graph)
    for i in range(node_len**2):
        ix_x1 = i // node_len
        ix_y1 = i % node_len
        if ix_x1 == ix_y1:
            continue
        for possible_pertubs in possible_weights - {graph[ix_x1][ix_y1]}:
            cc1_graph = deepcopy(graph)
            cc1_graph[ix_x1][ix_y1] = possible_pertubs
            for j in range(i + 1, node_len**2):
                ix_x2 = j // node_len
                ix_y2 = j % node_len
                if ix_x2 == ix_y2:
                    continue
                for possible_perturbs2 in possible_weights - {cc1_graph[ix_x2][ix_y2]}:
                    cc2_graph = deepcopy(cc1_graph)
                    cc2_graph[ix_x2][ix_y2] = possible_perturbs2
                    yield cc2_graph

优化的递归实现 #

下面是更简洁的递归版本，解决了上述问题，同时具备更好的可扩展性：

from copy import deepcopy

def generate_modifications(graph: list[list], num_changes: int, start_idx: int = 0):
    node_len = len(graph)
    possible_weights = {-1, 0, 1}
    
    if num_changes == 0:
        yield deepcopy(graph)
        return
    
    for i in range(start_idx, node_len ** 2):
        x = i // node_len
        y = i % node_len
        if x == y:
            continue
        
        original_val = graph[x][y]
        for new_val in possible_weights - {original_val}:
            # 复制当前图并修改
            modified_graph = deepcopy(graph)
            modified_graph[x][y] = new_val
            # 递归生成剩余修改，从下一个索引开始避免重复组合
            yield from generate_modifications(modified_graph, num_changes - 1, i + 1)

# 生成所有双边修改的图
def all_modification_generation(graph: list[list]):
    yield from generate_modifications(graph, num_changes=2)

递归版本的优势：

• 可扩展性：若后续需要生成k边修改的结果，只需调整num_changes参数，无需重写多层循环。
• 逻辑清晰：避免嵌套循环，代码结构更直观。
• 自动去重：通过start_idx参数确保每条修改组合只生成一次（不会出现先改边A再改B和先改B再改A的重复情况）。

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