首页 > 其他 > 详细

图的m染色问题

时间:2021-05-31 21:57:16      阅读:25      评论:0      收藏:0      [点我收藏+]

1.问题

给定无向连通图G和m种颜色,用这种颜色给图的顶点染色,每个顶点一种颜色。

如果要求G的每条边的两个顶点的颜色不相通同。如果存在, 给出所有可能的着色方案;如果不存在,则回答NO

2.解析

可以利用递归调用的思想,递归的去尝试填每一个点的颜色,再去判断当前的颜色是否符合情况,

如果符合情况就继续递归调用下去,不符合就退出。

当你的当前的节点数大于总的节点数,说明这是一种可以的情况,就退出。

3.设计

技术分享图片

 

 

4.分析

对于n个顶点,m种颜色复杂度是O(m^n)

5.源码

GitHub

 

图的m染色问题

原文:https://www.cnblogs.com/passawayy/p/14831833.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!