撬动offer：图的着色问题

BUG弄潮儿

发布于 2020-11-03 10:49:10

1.1K0

发布于 2020-11-03 10:49:10

文章被收录于专栏：JAVA乐园

0x01：说明

时长：两小时
考察点：算法实现能力，代码风格
注意，本题考察的是算法的实现而不是算法设计，算法的具体步骤已经在后面给出，只需实现给出的算法即可

0x02: 问题

图的着色问题图论和计算机科学的一个经典问题。给定一个无向图 G，为图中的每一个节点着色。一个合法的图着色方案必须要满足条件：任意两相邻节点的颜色不同。问题是，希望找到使用颜色数尽可能少的着色方案。如下图所示，一个包含 4 个节点的图，以及一种着色方案。这个着色方案使用了 3 种颜色，但不是最优的，可以找到只使用 2 种颜色的着色方案。

0x03：解法说明

要设计一个高效的寻找最优图着色方案的算法是非常困难的。下面提供一个近似算法，这个算法不一定给出一个最优的着色方案，但是可以给出一个较优的解。具体方法如下：

初始化未着色节点列表 U 为图的全部节点的列表
把未着色的节点列表 U 按照各节点未着色的邻接点的数目从大到小排序
选一个未使用的颜色 i，开始一轮着色，同时准备一个集合 Ci，后面会将所有用颜色 i 着色的节点加入到此集合
对排好序的 U 进行遍历，对遍历的节点依次尝试用颜色 i 进行着色 (当被遍历节点不与 Ci 中的任何一个节点邻接则可以用 i 着色)，若可以用 i 着色则把它加入集合 Ci， 若无法用 i 着色则跳过此节点
把集合 C 里面的所有节点从列表 U 中移除
重复进行 2–5，直到所有节点被着色

0x04：输入输出格式

输入

第一行有两个整数，第一个为图的节点数目，第二个为图的边的数目。从第二行开始，每一行用两个整数表示这个图的一条边，这两个整数是组成这条边的两个节点的 ID(节点 ID 从 0 开始编号)。

输出

第一行用一个整数表示使用的颜色数。第二行。按照节点 ID 从小到大，依次列出各节点的颜色编号 (颜色从 0 开始编号)。

例子

额外提供了一个项目骨架，大概结构如下

查看README.md说明，如下图

这个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;
    }

    @Override
    public 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<Integer, Set<Integer>> rowDataMap = Utils.readRowData(DATA_FILE);

        // 上色过程
        Map<Integer, Integer> 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<Integer, Integer> process(Map<Integer, Set<Integer>> rowDataMap) {

        //着色情况
        Map<Integer, Integer> 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<Integer, Set<Integer>> rowDataMap, Map<Integer, Integer> resultMap, int color){
         while(rowDataMap.size() > 0){
            // 把未着色的节点列表 U 按照各节点未着色的邻接点的数目从大到小排序
            PointModel[] sortU = sortU(rowDataMap);
            List<PointModel> paintPoint = new ArrayList<>();
            for(int i=0; i<sortU.length; i++){
                PointModel pm = sortU[i];
                if(check(pm, paintPoint, rowDataMap)){
                    continue;
                }else{
                    paintPoint.add(pm);
                    //上色
                    resultMap.put(pm.getKey(), color);
                }
            }
            remove(rowDataMap, paintPoint); 
            color = color + 1;
            loop(rowDataMap, resultMap, color);
         }
     }

    /**
     * 移除
     * @param rowDataMap
     * @param paintPoint
     */
    private Map<Integer, Set<Integer>>  remove(Map<Integer, Set<Integer>> rowDataMap, List<PointModel> paintPoint) {
        if(paintPoint.size()>0){
            for(int i=0; i<paintPoint.size(); i++){
                rowDataMap.remove(paintPoint.get(i).getKey());
            }
        }
        return rowDataMap;
    }

    /**
     * 检查是否相邻
     * 
     * @param pm
     * @param paintPoint
     * @param rowDataMap
     * @return
     */
    private boolean check(PointModel pm, List<PointModel> paintPoint, Map<Integer, Set<Integer>> rowDataMap) {
        int key = pm.getKey();
        //获取key的所有相邻节点
        Set<Integer> set = rowDataMap.get(key);
        for(int i=0; i<paintPoint.size(); i++){
            if(set.contains(paintPoint.get(i).getKey())){
                return true;
            }
        }
        return false;
    }

    /**
     * 排序
     * 
     * @param rowDataMap
     * @return
     */
    private PointModel[] sortU(Map<Integer, Set<Integer>> rowDataMap){
        Set<Integer> U =rowDataMap.keySet();
        Iterator<Integer> iter = U.iterator();
        int index = 0;
        PointModel[] pms = new PointModel[rowDataMap.size()];
        while(iter.hasNext()){
            Integer key = iter.next();
            Set<Integer> values = rowDataMap.get(key);
            PointModel pm = new PointModel();
            pm.setKey(key);
            pm.setPointSize(values.size());
            pms[index] = pm;
            index = index + 1;
        }
        System.out.println(JSON.toJSONString(pms));
        quick_sort(pms, 0, pms.length-1);
//        PointModel[] result = new PointModel[pms.length];
//        int k = 0;
//        for(int i= pms.length; i > 0; i--){
//            result[k] = pms[i-1];
//            k = k + 1;
//        }
        return pms;
    }


  //快速排序
   private void quick_sort(PointModel[] pms , int l, int r)
    {
        if (l < r)
        {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r;
            PointModel    x = pms[l];
            while (i < j)
            {
                while(i < j && pms[j].getPointSize() <= x.getPointSize()) // 从右向左找第一个小于x的数
                    j--;  
                if(i < j) {
                    pms[i++] = pms[j];

                }

                while(i < j && pms[i].getPointSize() > x.getPointSize()) // 从左向右找第一个大于等于x的数
                    i++;  
                if(i < j) {
                    pms[j--] = pms[i];
                }
            }
            pms[i] = x;
            quick_sort(pms, l, i - 1); // 递归调用 
            quick_sort(pms, i + 1, r);
        }
    }

    /**
     * TODO 找出未上色的点里面，相邻点最多的。本方法可以修改，也可以不用本方法。
     */
    private void findNextPointToPaint() {

    }

}

相关代码已上传，如需下载如查看

https://blog.csdn.net/huangjinjin520

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-10-31，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 BUG弄潮儿微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

撬动offer：图的着色问题

撬动offer：图的着色问题

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐