撬动offer：图的着色问题
共 3339字，需浏览 7分钟
·
2020-11-02 08:01
点击上方「蓝字」关注我们
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 开始编号)。
例子
输入
4 3
0 1
1 2
1 3
输出:
3
0 1 2 2
额外提供了一个项目骨架，大概结构如下
查看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();
// 读取数据
MapSet > 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(MapSet> 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(MapSet> rowDataMap, Map resultMap, int color){
while(rowDataMap.size() > 0){
// 把未着色的节点列表 U 按照各节点未着色的邻接点的数目从大到小排序
PointModel[] sortU = sortU(rowDataMap);
List paintPoint = new ArrayList<>();
for(int i=0; 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 MapSet> remove(MapSet> rowDataMap, List paintPoint) {
if(paintPoint.size()>0){
for(int i=0; i rowDataMap.remove(paintPoint.get(i).getKey());
}
}
return rowDataMap;
}
/**
* 检查是否相邻
*
* @param pm
* @param paintPoint
* @param rowDataMap
* @return
*/
private boolean check(PointModel pm, List paintPoint, MapSet> rowDataMap) {
int key = pm.getKey();
//获取key的所有相邻节点
Set set = rowDataMap.get(key);
for(int i=0; i if(set.contains(paintPoint.get(i).getKey())){
return true;
}
}
return false;
}
/**
* 排序
*
* @param rowDataMap
* @return
*/
private PointModel[] sortU(MapSet> rowDataMap){
Set U =rowDataMap.keySet();
Iterator iter = U.iterator();
int index = 0;
PointModel[] pms = new PointModel[rowDataMap.size()];
while(iter.hasNext()){
Integer key = iter.next();
Set 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
扫码二维码
获取更多精彩
Java乐园
