python 回溯法 子集树模板 系列 —— 10、m着色问题

简介: 问题图的m-着色判定问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色?图的m-着色优化问题若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数。

问题

图的m-着色判定问题

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色?

图的m-着色优化问题

若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。

img_c25e53d64cd23eb48b065d88976ff49c.png

分析

解的长度是固定的,n。若x为本问题的一个解,则x[i]表示第i个节点的涂色编号。

可以将m种颜色看作每个节点的状态空间。每到一个节点,遍历所有颜色,剪枝,回溯。

不难看出,可以套用回溯法子集树模板。

代码


'''图的m着色问题'''


# 用邻接表表示图
n = 5  # 节点数
a,b,c,d,e = range(n) # 节点名称
graph = [
    {b,c,d},
    {a,c,d,e},
    {a,b,d},
    {a,b,c,e},
    {b,d}
]

m = 4  # m种颜色

x = [0]*n  # 一个解(n元数组,长度固定)注意:解x的下标就是a,b,c,d,e!!!
X = []     # 一组解


# 冲突检测
def conflict(k):
    global n,graph,x
    
    # 找出第k个节点前面已经涂色的邻接节点
    nodes = [node for node in range(k) if node in graph[k]]
    if x[k] in [x[node] for node in nodes]: # 已经有相邻节点涂了这种颜色
        return True
        
    return False # 无冲突
    

# 图的m着色(全部解)
def dfs(k): # 到达(解x的)第k个节点
    global n,m,graph,x,X
    
    if k == n: # 解的长度超出
        print(x)
        #X.append(x[:])
    else:
        for color in range(m): # 遍历节点k的可涂颜色编号(状态空间),全都一样
            x[k] = color
            if not conflict(k): # 剪枝
                dfs(k+1)
                
# 测试
dfs(a)   # 从节点a开始

效果图

img_9ec9083222ceff81e080690995a82fe8.jpg

目录
相关文章
|
Python
python 回溯法 记录
一直不是太理解回溯法,这几天集中学习了一下,记录如下。 回溯法有“通用的解题法”之称。 1.定义:  也叫试探法,它是一种系统地搜索问题的解的方法。 2.基本思想:  从一条路往前走,能进则进,不能进则退回来,换一条路再试。
3141 0
|
6月前
|
机器学习/深度学习 存储 设计模式
Python 高级编程与实战:深入理解性能优化与调试技巧
本文深入探讨了Python的性能优化与调试技巧,涵盖profiling、caching、Cython等优化工具,以及pdb、logging、assert等调试方法。通过实战项目,如优化斐波那契数列计算和调试Web应用,帮助读者掌握这些技术,提升编程效率。附有进一步学习资源,助力读者深入学习。
|
3月前
|
Python
Python编程基石:整型、浮点、字符串与布尔值完全解读
本文介绍了Python中的四种基本数据类型:整型(int)、浮点型(float)、字符串(str)和布尔型(bool)。整型表示无大小限制的整数,支持各类运算;浮点型遵循IEEE 754标准,需注意精度问题;字符串是不可变序列,支持多种操作与方法;布尔型仅有True和False两个值,可与其他类型转换。掌握这些类型及其转换规则是Python编程的基础。
200 33
|
2月前
|
数据采集 分布式计算 大数据
不会Python,还敢说搞大数据?一文带你入门大数据编程的“硬核”真相
不会Python,还敢说搞大数据?一文带你入门大数据编程的“硬核”真相
75 1
|
3月前
|
设计模式 安全 Python
Python编程精进:正则表达式
正则表达式是一种强大的文本处理工具,用于搜索、匹配和提取模式。本文介绍了正则表达式的语法基础,如`\d`、`\w`等符号,并通过实例展示其在匹配电子邮件、验证电话号码、处理日期格式等场景中的应用。同时,文章提醒用户注意性能、编码、安全性等问题,避免常见错误,如特殊字符转义不当、量词使用错误等。掌握正则表达式能显著提升文本处理效率,但需结合实际需求谨慎设计模式。
130 2
|
4月前
|
数据采集 安全 BI
用Python编程基础提升工作效率
一、文件处理整明白了,少加两小时班 (敲暖气管子)领导让整理100个Excel表?手都干抽筋儿了?Python就跟铲雪车似的,哗哗给你整利索!
112 11
|
6月前
|
人工智能 Java 数据安全/隐私保护
[oeasy]python081_ai编程最佳实践_ai辅助编程_提出要求_解决问题
本文介绍了如何利用AI辅助编程解决实际问题,以猫屎咖啡的购买为例,逐步实现将购买斤数换算成人民币金额的功能。文章强调了与AI协作时的三个要点:1) 去除无关信息,聚焦目标;2) 将复杂任务拆解为小步骤,逐步完成;3) 巩固已有成果后再推进。最终代码实现了输入验证、单位转换和价格计算,并保留两位小数。总结指出,在AI时代,人类负责明确目标、拆分任务和确认结果,AI则负责生成代码、解释含义和提供优化建议,编程不会被取代,而是会更广泛地融入各领域。
182 28
|
6月前
|
机器学习/深度学习 数据可视化 TensorFlow
Python 高级编程与实战:深入理解数据科学与机器学习
本文深入探讨了Python在数据科学与机器学习中的应用,介绍了pandas、numpy、matplotlib等数据科学工具,以及scikit-learn、tensorflow、keras等机器学习库。通过实战项目,如数据可视化和鸢尾花数据集分类,帮助读者掌握这些技术。最后提供了进一步学习资源,助力提升Python编程技能。
|
6月前
|
设计模式 机器学习/深度学习 前端开发
Python 高级编程与实战:深入理解设计模式与软件架构
本文深入探讨了Python中的设计模式与软件架构,涵盖单例、工厂、观察者模式及MVC、微服务架构,并通过实战项目如插件系统和Web应用帮助读者掌握这些技术。文章提供了代码示例,便于理解和实践。最后推荐了进一步学习的资源,助力提升Python编程技能。

热门文章

最新文章