Python随机图贪心着色适配问题：字典格式图传入时索引错误的解决求助

看起来你的问题根源在于随机图的节点是1-based（从1开始），但你的greedyColoring函数是按0-based（从0开始）的索引来初始化结果列表的，导致访问result[i]时超出了列表范围。

问题分析 #

你生成的随机图字典键是1,2,3,4,5，但调用greedyColoring(d, 5)时，函数内部应该是初始化了一个长度为5的result列表（索引范围0-4）。当循环处理节点5时，尝试访问result[5]，这显然超出了列表的最大索引，直接触发IndexError。

两个可行的解决方案 #

方案1：将随机图改为0-based节点

这是最简单的调整，直接让图的节点索引和函数的结果列表索引对齐：

from random import sample, randrange

# 把节点列表改为0起始
q = [0, 1, 2, 3, 4]
# 生成0-based的随机图字典
random_graph = {i: sample([j for j in q if i != j], randrange(1, len(q)-1)) for i in q}

# 调用贪心着色函数（此时num_vertices=5，对应0-4的索引）
greedyColoring(random_graph, 5)

方案2：修改greedyColoring函数适配1-based节点

如果不想改动图的节点格式，可以调整函数内部的结果列表初始化和遍历逻辑，适配1-based的节点：

def greedyColoring(graph, num_vertices):
    # 初始化结果列表，长度设为num_vertices+1（索引0不用，1-num_vertices对应节点）
    result = [-1] * (num_vertices + 1)
    
    # 遍历图中的每一个节点（1到num_vertices）
    for node in graph.keys():
        # 收集相邻节点已使用的颜色
        used_colors = set()
        for neighbor in graph[node]:
            if result[neighbor] != -1:
                used_colors.add(result[neighbor])
        
        # 找到第一个可用的颜色（从0开始尝试）
        current_color = 0
        while current_color in used_colors:
            current_color += 1
        result[node] = current_color
    
    # 返回结果（如果不需要索引0，可以返回result[1:]）
    return result

# 调用时保持原参数
greedyColoring(d, 5)

验证说明 #

调整后，无论是修改图的节点格式还是函数逻辑，都能让result的索引和图的节点一一对应，避免索引越界的问题，同时保证贪心着色算法正常运行。

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