神剑山庄资源网 Design By www.hcban.com
本文实例讲述了Python基于回溯法子集树模板解决m着色问题。分享给大家供大家参考,具体如下:
问题
图的m-着色判定问题
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色"//img.jbzj.com/file_images/article/201709/201797105649566.png" alt="" />
分析
解的长度是固定的,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开始
效果图
更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。
神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com
暂无Python基于回溯法子集树模板解决m着色问题示例的评论...
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
2024年10月03日
2024年10月03日
- 孙悦.1996-伙伴【正大国际】【WAV+CUE】
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】