Welsh-Powell图着色Python程序运行异常与输出不符问题求助

问题1：命令行参数错误 #

运行python main.py ./input.txt时触发IndexError: list index out of range，原因是未正确处理命令行参数缺失的情况。当用户未传入输入文件路径时，sys.argv仅包含脚本名一个元素，访问sys.argv[1]必然报错。

问题2：着色结果与预期不符 #

当前代码的着色逻辑不符合Welsh-Powell算法的核心步骤，同时存在邻居颜色判断的错误，导致输出结果偏离预期。

修复步骤 #

1. 修复命令行参数检查 #

修改main.py，添加参数校验逻辑，确保用户传入输入文件路径，同时新增结果写入文件的功能：

from graphColoring import file_to_graph, color_graph
import sys

if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("用法: python main.py <输入文件路径>")
        sys.exit(1)
    graph = file_to_graph(sys.argv[1])
    colored_vertexes = color_graph(graph)
    # 输出到控制台并写入文件
    with open("output.txt", "w") as f:
        for colored_vertex in sorted(colored_vertexes, key=lambda x: x[0]):
            line = f"{colored_vertex[0]} {colored_vertex[1]}"
            print(line)
            f.write(line + "\n")

2. 修复输入文件读取逻辑 #

修改graphColoring.py中的file_to_graph函数，处理换行符和空行，避免解析错误：

def file_to_graph(filename):
    graph = [[], []]  # graph[0]存储[顶点, 度数]列表，graph[1]存储边列表
    with open(filename, 'r') as file1:
        for line in file1:
            line = line.strip()
            if not line:
                continue
            row = line.split()
            from_vertex = int(row[0])
            to_vertex = int(row[1])

            found_from = -1
            found_to = -1
            # 更新已有顶点的度数
            for i, (v, cnt) in enumerate(graph[0]):
                if v == from_vertex:
                    graph[0][i][1] += 1
                    found_from = i
                if v == to_vertex:
                    graph[0][i][1] += 1
                    found_to = i
            # 添加未存在的顶点
            if found_from == -1:
                graph[0].append([from_vertex, 1])
            if found_to == -1:
                graph[0].append([to_vertex, 1])
            # 记录边
            graph[1].append((from_vertex, to_vertex))
    return graph

3. 修复Welsh-Powell着色逻辑 #

重新实现color_graph函数，严格遵循算法步骤：

• 按顶点度数降序排序
• 逐个处理顶点，为每个顶点分配最小的未被已着色邻居使用的颜色

def get_color(colored_dict, vertex):
    return colored_dict.get(vertex, -1)

def color_graph(graph, max_colors=-1):
    # 按度数降序排序顶点
    sorted_vertexes = sorted(graph[0], key=lambda x: x[1], reverse=True)
    # 用字典存储顶点-颜色映射，提升查询效率
    colored_dict = {v: 0 for v, _ in sorted_vertexes}

    for v, _ in sorted_vertexes:
        # 收集已着色邻居的颜色集合
        neighbor_colors = set()
        for u, w in graph[1]:
            if u == v and colored_dict[w] != 0:
                neighbor_colors.add(colored_dict[w])
            if w == v and colored_dict[u] != 0:
                neighbor_colors.add(colored_dict[u])
        # 找到最小的可用颜色
        color = 1
        while color in neighbor_colors:
            color += 1
        # 可选：限制最大颜色数
        if max_colors != -1 and color > max_colors:
            raise ValueError("无法用指定数量的颜色完成着色")
        colored_dict[v] = color

    # 转换为原接口要求的列表格式返回
    return [[v, c] for v, c in colored_dict.items()]

测试结果 #

使用提供的input.txt运行修正后的程序，输出与预期完全一致：

1 2
2 1
3 2
4 3
5 3
6 4
7 5
8 3
9 1
10 2
11 6
12 6

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