如何在NetworkX中修改DSatur算法以指定颜色数完成图着色

你的核心需求是保留DSatur优先调度高约束节点的排序逻辑，同时强制使用满512种颜色（对应512个考试时段），不需要改动DSatur本身的节点优先级排序规则，只要调整着色阶段的选色逻辑即可。

修改思路 #

• 原生DSatur默认选择第一个不与邻居冲突的最小序号颜色，最终色数只会略高于图本身的色数，远达不到512的要求
• 完全保留原有DSatur的节点输出顺序：始终优先选择饱和度最高、节点度数最高的考试先排，完全匹配你需要的高冲突考试优先调度的规则
• 调整选色逻辑，把可选颜色范围限定在0~511之间，优先选择还未被使用过的颜色直到512个颜色全部被启用，所有颜色启用后选择当前已分配考试最少的可用颜色，兼顾时段负载均匀
• 你的图最高节点度数为203，任意节点的邻居最多占用203种不同颜色，512个可用颜色永远有至少309个可选值，不存在无颜色可分配的可行性问题

修改后可直接运行的代码 #

import itertools
from collections import Counter

def coloring_algorithm(G, fixed_color_num=512):
    if len(G) == 0:
        return {}
    colors = {}
    color_usage = Counter()  # 记录每个时段已分配的考试数量
    nodes = DSatur(G, colors)
    for u in nodes:
        # 收集当前节点邻居已经占用的颜色
        neighbour_colors = {colors[v] for v in G[u] if v in colors}
        # 筛选所有不冲突的可用时段
        available_colors = [c for c in range(fixed_color_num) if c not in neighbour_colors]
        # 优先选还没被用过的时段，直到凑满512个时段
        unused_colors = [c for c in available_colors if color_usage[c] == 0]
        if unused_colors:
            selected_color = unused_colors[0]
        else:
            # 所有时段都启用后，选当前考试最少的时段，平衡负载
            selected_color = min(available_colors, key=lambda c: color_usage[c])
        colors[u] = selected_color
        color_usage[selected_color] += 1
    return colors


def DSatur(G, colors):
    distinct_colors = {v: set() for v in G}
    total_nodes = len(G)
    for i in range(total_nodes):
        if i == 0:
            # 第一个节点选度数最高的，和原生DSatur逻辑一致
            node = max(G, key=G.degree)
            yield node
            for v in G[node]:
                distinct_colors[v].add(0)
        else:
            saturation = {
                v: len(c) for v, c in distinct_colors.items() if v not in colors
            }
            # 优先级：饱和度高>度数高，完全保留DSatur的排序规则
            node = max(saturation, key=lambda v: (saturation[v], G.degree(v)))
            yield node
            assigned_color = colors[node]
            for v in G[node]:
                distinct_colors[v].add(assigned_color)

效果说明 #

• 最终返回的着色结果一定用满0~511的全部512个颜色，不会出现颜色数不足的问题
• 高冲突、多学生选修的考试会被优先安排，符合排课优先级逻辑
• 各时段的考试数量会尽可能均匀，不会出现极端负载情况

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