生活_傻大方

  1. 首页 > 潮·科技 > >

撬动offer：图的着色问题

0x01：说明

  • 时长：两小时
  • 考察点：算法实现能力 ， 代码风格
  • 注意 ， 本题考察的是算法的实现而不是算法设计 ， 算法的具体步骤已经在后面给出 ， 只需实现给出的算法即可
0x02: 问题图的着色问题图论和计算机科学的一个经典问题 。给定一个无向图 G ， 为图中的每一个节点着色 。 一个合法的图着色方案必须要满足条件：任意两相邻节点的颜色不同 。 问题是 ， 希望找到使用颜色数尽可能少的着色方案 。 如下图所示 ， 一个包含 4 个节点的图 ， 以及一种着色方案 。 这个着色方案使用了 3 种颜色 ， 但不是最优的 ， 可以找到只使用 2 种颜色的着色方案 。
撬动offer：图的着色问题文章插图
0x03：解法说明要设计一个高效的寻找最优图着色方案的算法是非常困难的 。 下面提供一个近似算法 ， 这个算法不一定给出一个最优的着色方案 ， 但是可以给出一个较优的解 。 具体方法如下：
初始化未着色节点列表 U 为图的全部节点的列表 把未着色的节点列表 U 按照各节点未着色的邻接点的数目从大到小排序 选一个未使用的颜色 i ， 开始一轮着色 ， 同时准备一个集合 Ci ， 后面会将所有用颜色 i 着色的节点加入到此集合 对排好序的 U 进行遍历 ， 对遍历的节点依次尝试用颜色 i 进行着色 (当被遍历节点不与 Ci 中的任何一个节点邻接则可以用 i 着色) ，若可以用 i 着色则把它加入集合 Ci ，若无法用 i 着色则跳过此节点 把集合 C 里面的所有节点从列表 U 中移除 重复进行 2–5 ， 直到所有节点被着色
0x04：输入输出格式输入 第一行有两个整数 ， 第一个为图的节点数目 ， 第二个为图的边的数目 。 从第二行开始 ， 每一行用两个整数表示这个图的一条边 ， 这两个整数是组成这条边的两个节点的 ID(节点 ID 从 0 开始编号) 。输出 第一行用一个整数表示使用的颜色数 。 第二行 。 按照节点 ID 从小到大 ， 依次列出各节点的颜色编号 (颜色从 0 开始编号) 。例子
输入4 30 11 21 3输出: 30 1 2 2复制代码额外提供了一个项目骨架 ， 大概结构如下
撬动offer：图的着色问题文章插图
查看README.md说明 ， 如下图
撬动offer：图的着色问题文章插图
这个README.md是对项目的类文件介绍的 。
0x05：具体实现定义一个模型 ， key代表节点 ， pointSize代表该节点相邻节点的个数
package color;import com.alibaba.fastjson.JSON;public class PointModel {private Integer key;private Integer pointSize;public Integer getKey() {return key;}public void setKey(Integer key) {this.key = key;}public Integer getPointSize() {return pointSize;}public void setPointSize(Integer pointSize) {this.pointSize = pointSize;}@Overridepublic String toString() {return JSON.toJSONString(this);}}复制代码核心实现类
package color;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Set;import com.alibaba.fastjson.JSON;/** * @author aac */public class Question {/*** 答题者需要将 6 个数据集都跑一次 。* gc_4_1* gc_20_1* gc_50_5* gc_50_7* gc_100_5* gc_1000_5*/private static final String DATA_FILE = "gc_50_7";/*** 主流程 。 答题者请勿修改此方法 。*/public static void main(String[] args) {Question question = new Question();// 读取数据Map> rowDataMap = Utils.readRowData(DATA_FILE);// 上色过程Map paintResult = question.process(rowDataMap);// 输出到文件Utils.usePrintWriter(paintResult, DATA_FILE);// 检测Utils.validate(DATA_FILE);}/*** 给点涂色的过程 。** @param rowDataMap 点阵数据 。 这个数据已经有值了 。 不用再取获取 。 其中的 key 就代表点 ，*value 是个 Set ， 代表和 key 里面的点相连的其他点 。* @return 返回的结果也是个 map ， 里面的 key 代表点 ， value 代表点的颜色 。*/private Map process(Map> rowDataMap) {//着色情况Map resultMap = new HashMap<>();int color = 0;loop(rowDataMap, resultMap, color);///*//* TODO 答题者需要做的就是填充这个 Map 。 比如这里用了一个正确的答案 。 现在直接运行这个类是可以跑通的 。 //*但是答题者需要写出正确的算法 ， 使得本算法可以分别算出6组数据的解 。 //*///resultMap.put(0, 1);//resultMap.put(1, 0);//resultMap.put(2, 1);//resultMap.put(3, 1);return resultMap;}/**** @param rowDataMap* @param resultMap* @param color*/public void loop(Map> rowDataMap, Map resultMap, int color){while(rowDataMap.size() > 0){// 把未着色的节点列表 U 按照各节点未着色的邻接点的数目从大到小排序PointModel[] sortU = sortU(rowDataMap);List paintPoint = new ArrayList



上一篇：前所未见的饼干多米诺骨牌来了！凯度双热风蒸烤一体机挑战极致均匀

下一篇：小米新品发布，到手价1499元：买了，就是买健康