如何调整Python图着色代码使节点a和f颜色不同？

问题根因 #

你当前代码中a和f颜色相同的核心原因是邻接表没有将a和f定义为相邻节点，原有图着色逻辑仅校验相邻节点颜色不能重复，对非相邻节点无约束，因此二者同色符合现有代码逻辑。

解决方案 #

根据你的实际需求二选一即可：

方案1：a和f本应为相邻节点（漏写邻接关系）

直接更新邻接表，给两个节点互相添加为邻居即可，无需修改其他逻辑：

neighbours = {}
neighbours['a'] = ['b', 'c','d','e', 'f'] # 新增f为a的邻居
neighbours['b'] = ['a', 'f', 'd']
neighbours['c'] = ['a', 'f', 'd']
neighbours['d'] = ['a', 'f', 'b']
neighbours['e'] = ['a', 'c', 'f']
neighbours['f'] = ['b', 'c', 'd', 'e', 'a'] # 新增a为f的邻居

方案2：a和f确实不相邻，但业务要求必须颜色不同

无需修改邻接表，直接在校验函数中新增a和f的同色拦截规则即可：

def promising(vertice, colour):
    for neighbour in neighbours.get(vertice): 
        colour_of_neighbour = colours_of_vertices.get(neighbour)
        if colour_of_neighbour == colour:
            return False
    # 新增a和f不同色的特殊校验
    if (vertice == 'a' and colours_of_vertices.get('f') == colour) or (vertice == 'f' and colours_of_vertices.get('a') == colour):
        return False
    return True

修改完成后重新运行代码，输出的a和f颜色就会不同。

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