图的M着色算法演示ppt.ppt

图的m着色问题 讲课 吴双燕PPT制作 谭晓雅 目录 问题产生的背景 问题描述 程序运行及结果 四 一 二 三 算法设计与分析 图的着色问题是由地图的着色问题引申而来的 用m种颜色为地图着色 使得地图上的每一个区域着一种颜色 且相邻区域颜色不同 一 产生背景 二 问题描述 给定无向连通图G和m种不同的颜色 用这些颜色为图G的各顶点着色 每个顶点着一种颜色 是否有一种着色法使G中每条边的2个顶点着不同颜色 如果有则称这个图是m可着色 否则称这个图不是m可着色 若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色 则称这个数k为该图的色数 三 算法设计 输入 颜色种类m输出 如果这个图不是m可着色 给出否定回答 如果这个图是m可着色的 找出所有不同的着色法 1 4 2 3 可以用一下邻接矩阵来表示 1111011111111101111101011 邻接矩阵中通常用二维数组来存放边之间的关系 用一维数组来存放顶点的信息 所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻 用一维数组x来存放每个顶点的颜色 x i j表示第i个节点图第j中颜色 5 我们可以把问题简化为3个点来分析 现给定如下图 怎样求解呢 1 2 3 该图的色数是多少 怎样用解空间树来表示呢 由图可知 对于每一个顶点可选的颜色可以有3种不同的选择 所以每一个节点有3个儿子节点 有4层 判断条件是什么 新加入来得节点t取某一种颜色i时 依次和上层的每一个节点j j t 比较 如果a t j 1并且x t x j 那么它是不可着色的 intOK intt inti intj for j 1 j t j if a t j 2020 3 10 10 可编辑 模拟演示 t 1 t 2 t 3 t 4 voidBacktrace intt intm 当前节点 颜色的种类 当搜索的当前节点t N时 m种颜色依次试用 调用函数OK进行判断 如果当前颜色可以 则进入下一层搜索 当搜索到最叶子节点时 t N 即可输出一种方案 for i 1 i m i if OK t i x t i Backtrace t 1 m if t N sum printf 第 d种方案 n sum for i 1 i N i printf d x i 四 程序代码 include include defineN3 图中节点的个数inta N 1 N 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 邻接矩阵intx N 1 记录颜色intsum 0 保存可以着色的方案数intOK intt inti 判断函数 intj for j 1 j t j if a t j voidBacktrace intt intm inti if t N 算法搜索至叶子节点 sum printf 第 d种方案 n sum for i 1 i N i printf d x i printf n else for i 1 i m i if OK t i x t i Backtrace t 1 m intmain intm inti printf 请输入颜色种类 n scanf d 运行结果 当N 5时 色数又是多少呢 X 1 1 X 1 4 X 1 2