图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色.问是否存在着色方法,使得G中任2邻接点有不同颜色。
图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。
若图G是可平面图,则它的色数不超过4色(4色定理).
4色定理的应用:在一个平面或球面上的任何地图能够只用4种
颜色来着色使得相邻的国家在地图上着有不同颜色
任意图的着色
Welch Powell法
a).将G的结点按照度数递减的次序排列.
b).用第一种颜色对第一个结点着色,并按照结点排列的次序
对与前面着色点不邻接的每一点着以相同颜色.
c).用第二种颜色对尚未着色的点重复步骤b).用第三种颜色
继续这种作法, 直到所有点着色完为止.
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespacestd;
int map[10][10];//邻接矩阵
typedef structNode{ //定义节点结构体
int index; //编号
int degree; //度
int color; //改节点的颜色
} Node;
Nodenodes[10];
bool com(Nodenode1,Nodenode2) { //按度从高到低排序
return node1.degree > node2.degree;
}
bool com2(Nodenode1,Nodenode2) { //按度从高到低排序
return node1.index < node2.index;
}
int main() {
ifstream read;
read.open("map.data");//map.data是存放数据的文件名
int m, n;
while (read >> m>> n) {
for (int i = 0; i < m; i++) {//读入数据
int degree = 0;
for (int j = 0; j < n; j++) {
read>> map[i][j];
if (map[i][j])
degree++;
}
nodes[i].index = i;
nodes[i].degree = degree;
nodes[i].color = 0;
}
//排序
sort(nodes,nodes + m, com);
int k = 0;//K 代表第几种颜色
while (true) {
k++;
int i;
for (i = 0; i < m; i++){//先找到第一个未着色的节点
if (nodes[i].color == 0) {
nodes[i].color = k;
break;
}
}
if (i == m)//循环退出的条件,所有节点都已着色
break;
//再把所有不和该节点相邻的节点着相同的颜色
for(int j=0; j<m; j++){
if(nodes[j].color ==0 &&map[nodes[i].index][nodes[j].index] == 0
&&i!=j)
nodes[j].color = k;
}
}
//输出结果:
sort(nodes,nodes + m, com2);
cout << "共需要" << k-1 << "种颜色" << endl;
for (int i = 0; i < m; i++)
cout<< "节点:"<<nodes[i].index <<":着色" << nodes[i].color <<endl;
return 0;
}
}
测试数据(map.data):
8 8
0 1 1 1 0 0 1 0
1 0 1 1 1 0 0 0
1 1 0 0 1 1 0 0
1 1 0 0 1 0 1 0
0 1 1 1 0 1 1 1
0 0 1 0 1 0 0 1
1 0 1 1 1 0 0 1
0 0 0 0 1 1 10
即:
运行结果;
共需要3种颜色
节点:1:着色1
节点:2:着色2
节点:3:着色3
节点:4:着色3
节点:5:着色1
节点:6:着色2
节点:7:着色2
节点:8:着色3
分享到:
相关推荐
贪心法求解图的着色问题C++源代码,可直接编译运行。 greedy.
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
综合运用贪心算法,求解不同数目的找零钱问题的源程序
任意输入城市数目,然后输入各城市间距离,运行显示各条旅行路线 使用贪心算法,找出次优解
用贪心算法求解最优服务次序问题,计算机算法设计与分析
活动安排问题是利用贪心算法有效求解的很好例子。该问题要求高校的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法,使尽可能多的活动可以兼容的使用某一公共资源
贪心算法求解最少硬币问题C语言程序,问题描述:给顾客找零钱时,收银处有1元,5角和1角硬币若干,如何用最少数量的硬币找够零钱? 算法思想:比如要找给顾客2元9角钱,首先计算1元最多可以有多少枚,即2枚,减去2元,还...
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
C++应用贪心算法求解背包问题,可用于算法课程设计答辩。
贪心算法 背包问题 c语言 绝对无误 运行成功
利用贪心算法求解背包问题,运行通过可行,注释完整,是初学者理解贪心算法的好帮手,好资源一起分享,希望可以帮助大家
多机调度问题的贪心算法实现。示例代码,可直接在VC上运行。
图的着色,贪心算法,数据结构
C++应用贪心算法求解背包问题.docx
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0编译通过 有几个实验为C语言代码 还有...
贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
地图着色的算法,能够实现地图的输入,并形成着色方案,用贪心算法实现,值得参考
2.领域:智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,更多内容可点击博主头像 3.内容:标题所示,对于介绍可点击主页搜索博客 4.适合人群:本科,硕士...
0-1背包问题(贪心算法)C语言源程序. 物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。