日撸Java三百行(day35:图的m着色问题)

2024-08-27 07:36
文章标签 java 问题 着色 三百 day35

本文主要是介绍日撸Java三百行(day35:图的m着色问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

一、问题描述

二、思路分析

三、代码实现

总结


一、问题描述

在高中学习排列组合的时候,有一个非常经典的问题,就是涂色问题,即用m种颜色给n块区域涂色,要求每块区域只能涂同一种颜色且相邻区域的颜色不能相同,问一共有多少种涂色方案。还记得当时自己是怎么做的吗?下面我们就用一个具体的例子来回顾一下。

如下图,共有A、B、C、D四块区域,用五种颜色给它们涂色,要求每块区域只能涂同一种颜色且相邻区域的颜色不能相同,请问一共有多少种涂色方案?

采用枚举法,第一步,给A区域涂色,由于A区域是第一个涂色的区域,没有任何颜色限制,所以有5种方法; 第二步,给B区域涂色,B区域与A区域相邻,使得B区域不能涂A区域涂过的颜色,所以共有4种方法;第三步,给C区域涂色,C区域与B区域相邻,使得C区域不能涂B区域涂过的颜色,所以共有4种方法;第四步,给D区域涂色,D区域与B、C区域都相邻,使得D区域不能涂B、C区域涂过的颜色,所以共有3种方法。最后,根据分步乘法计数原理,得到共有5*4*4*3=240种方案。

如果这只是高中的一道数学题,那必然不会放到这里来说,所以接下来我们就要将它抽象成图。显然,一块一块的区域可以看作图的一个个节点,因此给区域涂色就是给节点涂色,要求相邻区域的颜色不能相同就是要求邻接节点的颜色不能相同,所以上述例子就可以改写如下(区域与区域相邻显然是一个双向相邻,所以这里我们需要用到的是无向图):

 这也就是今天我们要讨论的问题——图的m着色问题。

二、思路分析

那么该如何来解决这个问题呢?对于排列组合给区域涂色的问题,我们使用的是枚举法,同理,图的m着色问题我们同样可以使用枚举法(穷举法)来解决,也就是使用暴力解题法来完成。仍然以上图为例,进行具体说明:

  • 将A、B、C、D四个节点编号为0、1、2、3号节点,将五种颜色编号为0、1、2、3、4号颜色,然后开始涂色。
  • 假设从0号节点开始涂色0号颜色,那么1号节点可以涂1、2、3、4号颜色。
  • 如果1号节点涂色1号颜色,那么2号节点可以涂色0、2、3、4号颜色;如果1号节点涂色2号颜色,那么2号节点可以涂色0、1、3、4号颜色;如果1号节点涂色3号颜色,那么2号节点可以涂色0、1、2、4号颜色;如果1号节点涂色4号颜色,那么2号节点可以涂色0、1、2、3号颜色。
  • 如果1号节点涂色1号颜色,2号节点涂色0号颜色,那么3号节点可以涂色2、3、4号颜色;如果1号节点涂色1号颜色,2号节点涂色2号颜色,那么3号节点可以涂色0、3、4号颜色;如果1号节点涂色1号颜色,2号节点涂色3号颜色,那么3号节点可以涂色0、2、4号颜色……

以上就是这个问题的暴力解题法。

接下来,我们思考如何用代码来实现。如下图,仍然对节点和颜色分别进行从0开始的编号,并以节点总数为长度设置一个颜色标记数组,这样一来颜色标记数组的下标就与节点的编号达成了一致;颜色标记数组中的具体元素使用颜色编号来填充,这样通过数组下标就可以知道几号节点涂色了几号颜色;再设置一个默认初始值-1用于表示节点还未被涂色。

然后,我们从左往右(即从下标为0的节点开始)对颜色标记数组中的数据元素进行枚举,也就是用颜色编号进行填充,注意邻接节点在颜色标记数组中对应的位置不能存放相同的颜色编号。

我们暂时就分析到这里,剩下的内容在下面的代码实现过程中再继续。

三、代码实现

首先,进行初始化,如下:

    /************************ Coloring. Output all possible schemes.* * @param paraNumColors The number of colors.**********************/public void coloring(int paraNumColors) {// Step 1. Initialize.int tempNumNodes = connectivityMatrix.getRows();int[] tempColorScheme = new int[tempNumNodes];Arrays.fill(tempColorScheme, -1);

同样利用connectivityMatrix.getRows()获得节点总数tempNumNodes,然后将其作为数组长度创建一个int类型的颜色标记数组tempColorScheme,最后利用Array.fill()方法对tempColorScheme填充默认初始值-1。

补充:

Array.fill(数组名,默认初始值)方法:用于对一个数组快速填充同一默认初始值

然后,创建关键方法(其实也是对上面coloring方法的一个重载),如下:

    /************************ Coloring. Output all possible schemes.* * @param paraNumColors The number of colors.* @param paraCurrentNumNodes The number of nodes that have been colored.* @param paraCurrentColoring The array recording the coloring scheme.**********************/public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) {// Step 1. Initialize.int tempNumNodes = connectivityMatrix.getRows();System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "+ paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring));// A complete scheme.if (paraCurrentNumNodes >= tempNumNodes) {System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));return;} // Of if// Try all possible colors.for (int i = 0; i < paraNumColors; i++) {paraCurrentColoring[paraCurrentNumNodes] = i;if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) {coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);} // Of if} // Of for i} // Of coloring

该方法输入了三个参数,其中paraNumColors表示一共有几种颜色,paraCurrentNumNodes表示当前涂色节点的编号(即当前涂色节点在颜色标记数组中的对应下标),paraCurrentColoring表示当前的颜色标记数组。然后,通过一条输出语句将此时三个参数的值进行输出。

在程序运行过程中,逐步向颜色标记数组输入颜色编号,当paraCurrentNumNodes >= tempNumNodes即当前涂色节点的编号 >= 节点总数时,说明所有的节点均已完成了一次涂色,也就是说找到了一种涂色方案,此时直接输出结果(即输出当前的颜色标记数组)。

当paraCurrentNumNodes没有大于等于tempNumNodes即当前涂色节点的编号没有大于等于节点总数时,则进入循环,对节点进行涂色。在for循环中paraCurrentColoring[paraCurrentNumNodes] = i 表示将 i 号颜色的编号 i 输入当前涂色节点在颜色标记数组中的对应位置,相当于给当前涂色节点涂上 i 号颜色;接着,借助一个if语句,使得当涂色不冲突时继续给编号加1的节点(相当于在颜色标记数组中向右移动一格)进行涂色,而当涂色冲突时则给当前涂色节点涂上 i + 1 号颜色后,再次进行涂色冲突判断。

创建一个判断涂色是否冲突的方法,如下:

    /************************ Coloring conflict or not. Only compare the current last node with previous* ones.* * @param paraCurrentNumNodes The current number of nodes.* @param paraColoring        The current coloring scheme.* @return Conflict or not.**********************/public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) {for (int i = 0; i < paraCurrentNumNodes - 1; i++) {// No direct connection.if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) {continue;} // Of ifif (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {return true;} // Of if} // Of for ireturn false;} // Of colorConflict

connectivityMatrix.getValue()调用了之前整数矩阵类IntMatrix的getValue()方法,用于获得整数矩阵对象connectivityMatrix的某个具体元素值;然后利用了我们之前进行图的连通性检测的结论,即如果连通矩阵中某个元素的值为0,那么该元素行标对应的节点到该元素列标对应的节点不连通,不连通必然不邻接,也就不会发生涂色冲突,所以直接continue结束本次循环,返回false,代表涂色不冲突;但是如果paraColoring[paraCurrentNumNodes - 1] = paraColoring[ i ],则说明涂色会发生冲突,于是返回true。

最后,设置一个单元测试,如下:

    /************************ Coloring test.**********************/public static void coloringTest() {int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } };Graph tempGraph = new Graph(tempMatrix);// tempGraph.coloring(2);tempGraph.coloring(3);} // Of coloringTest

完整的程序代码:

    /************************ Coloring. Output all possible schemes.* * @param paraNumColors The number of colors.**********************/public void coloring(int paraNumColors) {// Step 1. Initialize.int tempNumNodes = connectivityMatrix.getRows();int[] tempColorScheme = new int[tempNumNodes];Arrays.fill(tempColorScheme, -1);coloring(paraNumColors, 0, tempColorScheme);} // Of coloring/************************ Coloring. Output all possible schemes.* * @param paraNumColors The number of colors.* @param paraCurrentNumNodes The number of nodes that have been colored.* @param paraCurrentColoring The array recording the coloring scheme.**********************/public void coloring(int paraNumColors, int paraCurrentNumNodes, int[] paraCurrentColoring) {// Step 1. Initialize.int tempNumNodes = connectivityMatrix.getRows();System.out.println("coloring: paraNumColors = " + paraNumColors + ", paraCurrentNumNodes = "+ paraCurrentNumNodes + ", paraCurrentColoring" + Arrays.toString(paraCurrentColoring));// A complete scheme.if (paraCurrentNumNodes >= tempNumNodes) {System.out.println("Find one:" + Arrays.toString(paraCurrentColoring));return;} // Of if// Try all possible colors.for (int i = 0; i < paraNumColors; i++) {paraCurrentColoring[paraCurrentNumNodes] = i;if (!colorConflict(paraCurrentNumNodes + 1, paraCurrentColoring)) {coloring(paraNumColors, paraCurrentNumNodes + 1, paraCurrentColoring);} // Of if} // Of for i} // Of coloring/************************ Coloring conflict or not. Only compare the current last node with previous* ones.* * @param paraCurrentNumNodes The current number of nodes.* @param paraColoring        The current coloring scheme.* @return Conflict or not.**********************/public boolean colorConflict(int paraCurrentNumNodes, int[] paraColoring) {for (int i = 0; i < paraCurrentNumNodes - 1; i++) {// No direct connection.if (connectivityMatrix.getValue(paraCurrentNumNodes - 1, i) == 0) {continue;} // Of ifif (paraColoring[paraCurrentNumNodes - 1] == paraColoring[i]) {return true;} // Of if} // Of for ireturn false;} // Of colorConflict/************************ Coloring test.**********************/public static void coloringTest() {int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } };Graph tempGraph = new Graph(tempMatrix);// tempGraph.coloring(2);tempGraph.coloring(3);} // Of coloringTest/************************ The entrance of the program.* * @param args Not used now.**********************/public static void main(String args[]) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFirstTraversalTest();depthFirstTraversalTest();coloringTest();} // Of main

部分运行结果:

总结

对于图的m着色问题,我们使用的是枚举法,也是一种暴力解题法。对于人来说,枚举法似乎看起来是一种“笨方法”,因为它没有特别高的技术含量而且还很繁琐,但是对于计算机而言则不然,暴力解题法的逻辑相对简单直接,利用计算机比较容易实现,而且当规模不是很多的时候,暴力解题法可能比复杂的优化算法更为高效。总之,学习计算机万能的暴力解题法是必不可少的。

这篇关于日撸Java三百行(day35:图的m着色问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1111042

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis