实现图支配集算法时遇列表索引越界及类型错误求解决

你要实现的支配集算法步骤如下：

1. 初始化空集合S
2. 选取图中任意边e，其连接顶点A和B
3. 将A或B其中一个顶点加入集合S
4. 删除图中所有与该顶点相连的边
5. 若图中仍有剩余边，重复步骤2
   最终集合S即为图的支配集。

你编写的多版代码均出现错误，以下是问题分析和修复方案：

第一版代码错误分析 #

第一版代码：

import random

S = []
while( len(edges) != 0):
   e = random.randint(0,len(edges)-1)
   k = random.randint(0,1)
   Vert = edges[e][k]
   print(Vert)
   S.append(Vert)           

   for i in range(len(edges)):
       for j in range(2):
           if edges[i][j] == Vert:
              edges.pop([i][0])
if edges[i][j] == Vert:

错误：IndexError: list index out of range
原因：

• 遍历edges时直接执行pop修改列表，会导致后续循环的索引与实际列表长度不匹配，比如初始长度为n，删除元素后长度变为n-1，但循环仍基于初始n的索引范围，访问时会超出边界。
• edges.pop([i][0])写法错误，pop需要传入整数索引，此处[i][0]完全多余，应直接写i。
• 最后一行孤立的if edges[i][j] == Vert:无意义，且此时i、j已超出循环作用域，必然触发索引错误。

第二版代码错误分析 #

第二版代码：

import random

S = []  # Dominating Set

while( len(edges) != 0):
    e = random.randint(0,len(edges)-1)
    k = random.randint(0,1)
    Vert = edges[e][k]
    print(Vert)
    S.append(Vert)           

    for i in range(len(edges)):
            if Vert in edges[i]:
                edges.pop([i]) 

错误：TypeError: 'list' object cannot be interpreted as an integer
原因：edges.pop([i])传入的是列表[i]，但pop要求参数为整数索引，应改为edges.pop(i)；同时依然存在遍历中修改列表导致的索引失效问题。

第三版代码错误分析 #

第三版代码片段：

size = len(edges)
i = 0
while( size != i):
    for j in range(2):
        if edges[i][j] == Vert:
            edges.pop([i][0])
            size = size-1
            i = 0
        else:
            i = i+1

错误：索引越界
原因：

• 内层for j循环中，若当前边不包含Vert，i会被连续加两次（j=0和j=1各一次），导致跳过元素或直接超出列表索引范围。
• edges.pop([i][0])依然是错误写法，应改为edges.pop(i)。
• 删除元素后重置i=0的逻辑混乱，容易引发重复遍历或索引错位。

正确的代码实现 #

核心解决思路：避免在遍历原列表时直接修改它，改用生成新列表过滤元素的方式，逻辑更清晰且不易出错。

import random

def find_dominating_set(edges):
    # 复制原边列表，避免修改输入的原始数据
    remaining_edges = edges.copy()
    dominating_set = []
    
    while remaining_edges:
        # 随机选取一条边
        edge_index = random.randint(0, len(remaining_edges)-1)
        selected_edge = remaining_edges[edge_index]
        # 随机选取边中的一个顶点
        selected_vertex = random.choice(selected_edge)
        dominating_set.append(selected_vertex)
        
        # 过滤掉所有包含该顶点的边，生成新的剩余边列表
        remaining_edges = [edge for edge in remaining_edges if selected_vertex not in edge]
    
    return dominating_set

# 测试示例
sample_edges = [(0, 2), (0, 3), (0, 4), (1, 2), (2, 3), (2, 4), (3, 4)]
result = find_dominating_set(sample_edges)
print("支配集:", result)

代码说明 #

1. 使用列表推导式过滤边，直接生成不含目标顶点的新列表，彻底避免了遍历中修改原列表的索引问题。
2. 用random.choice(selected_edge)替代手动生成0/1索引选顶点，代码更简洁易读。
3. 复制原边列表到remaining_edges，保护输入的原始数据不被修改。
4. 用while remaining_edges作为循环条件，列表为空时自动终止，比判断len(edges) != 0更简洁直观。

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