题目描述
通常，在十字交叉路口只需设红、绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。假设有一个如图(a)所示的五叉路口，其中C和E为单行道。在路口有13条可行的通路，其中有的可以同时通行，如A→B和E→C，而有的不能同时通行，如E→B和A→D。那么，在路口应如何设置交通灯进行车辆的管理呢？
思路分析
顶点图解释：
1.圈XY代表从道路X驶向道路Y的通道。
2.共有2×C（3，2）+4+3共13条通道。
3.若两通道不能同时通行，则将两通道相连。
问题转化为图着色问题
用最少的颜色对图着色<=>对尽可能多的点着以相同的颜色<=>让尽可能多的通道的车辆可以同时通行=>车流量最大
邻接矩阵
按图里从左到右从上到下的顺序对13个顶点从0~12依次标号，然后按照两顶点之间有边相连值为1，无边相连值为0的规则，得到邻接矩阵，如下：
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 1 0 0 0 1 1 0
1 1 0 0 0 1 0 0 0 0 1 1 0
0 1 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
算法
算法1：回溯法（深度优先搜索）
思路：
1.假设符合题意的最小颜色数是m
2.则每一个顶点可以涂m种颜色，共m^13种可能（包括合理和不合理的涂色方案）
3.采用深度优先搜索算法，找到合理的涂色方案，如果找不到则增加最小颜色数继续查找
该算法一定得到最优解，但时间复杂度高。
算法2：贪婪算法（Welch Powell算法）
1.将顶点按度数由大到小排列
2.对未涂色的度数最大的顶点涂色，并将与该顶点不相连且满足条件的其它顶点涂以相同的颜色
3.检查是否存在未涂色的顶点，若有，换一种颜色，重复2），否则，结束算法
该算法是启发式算法，时间复杂度低，但不一定得到最优解。
算法源码
算法1
#include <iostream>
using namespace std;
//颜色类
class Color {
public:
Color(int n,int **a,int *x,int sum);
bool ifOk(int node);
void Dfs(int node);
int n; //顶点数
int m; //可用颜色数
int **a; //邻接矩阵
int *x; //解向量
int sum; //可着色方案数
};
//构造函数
Color::Color(int n,int **a,int *x,int sum){
this->n=n;
this->a=a;
this->x=x;
this->sum=sum;
}
//判断顶点node是否可以涂色
bool Color::ifOk(int node) {
for (int i = 1; i <= n; i++)
if ((a[node-1][i-1] == 1) && x[node] == x[i])
return false;
return true;
}
//深度优先搜索
void Color::Dfs(int node) {
//当访问到叶子结点，则找到一种可着色方案 sum++
if (node > n) {
sum++;
//输出该涂色方案
for (int i = 1; i <= n; i++)
cout << x[i] << " ";
cout << endl;
}
//递归
else {
for (int i = 1; i <= m; i++) {
x[node] = i;
if (ifOk(node))
Dfs(node + 1);
x[node] = 0;
}
}
}
int main() {
//初始化邻接矩阵
int** graph=new int*[13];
for(int i=0;i<13;i++)
graph[i]=new int[13];
for (int i = 0;i < 13;i++)
for (int j = 0;j < 13;j++)
cin >> graph[i][j];
//初始化解向量
int* p=new int[14];
for(int i=0;i<14;i++)
p[i]=0;
//初始化颜色类
Color color(13,graph,p,0);
//涂色
int k=0;
while(true){
k++;
color.m=k;
color.Dfs(1);
if(color.sum!=0)
break;
}
//输出最小颜色数和涂色方案数
cout<<"最小颜色数m为："<<k<<endl;
cout<<"可行的涂色方案数为："<<color.sum;
}
编译运行：
$ g++ traffic11.cpp
$./a.out
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 1 0 0 0 1 1 0
1 1 0 0 0 1 0 0 0 0 1 1 0
0 1 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
......................................
4 4 4 4 3 3 1 1 3 1 2 2 1
4 4 4 4 3 3 1 1 3 1 2 2 2
4 4 4 4 3 3 1 1 3 1 2 2 3
4 4 4 4 3 3 1 1 3 1 2 2 4
4 4 4 4 3 3 1 1 3 2 2 2 1
4 4 4 4 3 3 1 1 3 2 2 2 2
4 4 4 4 3 3 1 1 3 2 2 2 3
4 4 4 4 3 3 1 1 3 2 2 2 4
4 4 4 4 3 3 1 1 3 3 2 2 1
4 4 4 4 3 3 1 1 3 3 2 2 2
4 4 4 4 3 3 1 1 3 3 2 2 3
4 4 4 4 3 3 1 1 3 3 2 2 4
4 4 4 4 3 3 1 1 4 1 2 2 1
4 4 4 4 3 3 1 1 4 1 2 2 2
4 4 4 4 3 3 1 1 4 1 2 2 3
4 4 4 4 3 3 1 1 4 1 2 2 4
4 4 4 4 3 3 1 1 4 2 2 2 1
4 4 4 4 3 3 1 1 4 2 2 2 2
4 4 4 4 3 3 1 1 4 2 2 2 3
4 4 4 4 3 3 1 1 4 2 2 2 4
4 4 4 4 3 3 1 1 4 3 2 2 1
4 4 4 4 3 3 1 1 4 3 2 2 2
4 4 4 4 3 3 1 1 4 3 2 2 3
4 4 4 4 3 3 1 1 4 3 2 2 4
4 4 4 4 3 3 2 2 1 1 1 1 1
4 4 4 4 3 3 2 2 1 1 1 1 2
4 4 4 4 3 3 2 2 1 1 1 1 3
4 4 4 4 3 3 2 2 1 1 1 1 4
4 4 4 4 3 3 2 2 1 2 1 1 1
4 4 4 4 3 3 2 2 1 2 1 1 2
4 4 4 4 3 3 2 2 1 2 1 1 3
4 4 4 4 3 3 2 2 1 2 1 1 4
4 4 4 4 3 3 2 2 1 3 1 1 1
4 4 4 4 3 3 2 2 1 3 1 1 2
4 4 4 4 3 3 2 2 1 3 1 1 3
4 4 4 4 3 3 2 2 1 3 1 1 4
4 4 4 4 3 3 2 2 2 1 1 1 1
4 4 4 4 3 3 2 2 2 1 1 1 2
4 4 4 4 3 3 2 2 2 1 1 1 3
4 4 4 4 3 3 2 2 2 1 1 1 4
4 4 4 4 3 3 2 2 2 2 1 1 1
4 4 4 4 3 3 2 2 2 2 1 1 2
4 4 4 4 3 3 2 2 2 2 1 1 3
4 4 4 4 3 3 2 2 2 2 1 1 4
4 4 4 4 3 3 2 2 2 3 1 1 1
4 4 4 4 3 3 2 2 2 3 1 1 2
4 4 4 4 3 3 2 2 2 3 1 1 3
4 4 4 4 3 3 2 2 2 3 1 1 4
4 4 4 4 3 3 2 2 3 1 1 1 1
4 4 4 4 3 3 2 2 3 1 1 1 2
4 4 4 4 3 3 2 2 3 1 1 1 3
4 4 4 4 3 3 2 2 3 1 1 1 4
4 4 4 4 3 3 2 2 3 2 1 1 1
4 4 4 4 3 3 2 2 3 2 1 1 2
4 4 4 4 3 3 2 2 3 2 1 1 3
4 4 4 4 3 3 2 2 3 2 1 1 4
4 4 4 4 3 3 2 2 3 3 1 1 1
4 4 4 4 3 3 2 2 3 3 1 1 2
4 4 4 4 3 3 2 2 3 3 1 1 3
4 4 4 4 3 3 2 2 3 3 1 1 4
4 4 4 4 3 3 2 2 4 1 1 1 1
4 4 4 4 3 3 2 2 4 1 1 1 2
4 4 4 4 3 3 2 2 4 1 1 1 3
4 4 4 4 3 3 2 2 4 1 1 1 4
4 4 4 4 3 3 2 2 4 2 1 1 1
4 4 4 4 3 3 2 2 4 2 1 1 2
4 4 4 4 3 3 2 2 4 2 1 1 3
4 4 4 4 3 3 2 2 4 2 1 1 4
4 4 4 4 3 3 2 2 4 3 1 1 1
4 4 4 4 3 3 2 2 4 3 1 1 2
4 4 4 4 3 3 2 2 4 3 1 1 3
4 4 4 4 3 3 2 2 4 3 1 1 4
最小颜色数m为：4
可行的涂色方案数为：92160
算法2：
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int index;
int degree;
int color;
};
//冒泡排序
void sort(Node* nodes) {
for (int i = 0;i < 13;i++) {
for (int j = 12;j > i;j--) {
if (nodes[j].degree > nodes[j - 1].degree) {
int degree = nodes[j - 1].degree;
int index = nodes[j - 1].index;
nodes[j - 1].degree = nodes[j].degree;
nodes[j - 1].index = nodes[j].index;
nodes[j].degree = degree;
nodes[j].index = index;
}
}
}
}
//按度数递减顺序输出排序后的顶点
void output(Node* nodes){
queue<int> q0,q1,q2,q3,q4,q5;
queue<int> q[6];
for(int i=0;i<13;i++)
q[nodes[i].degree].push(nodes[i].index);
for(int i=5;i>=0;i--){
cout<<"度数为"<<i<<"的顶点：";
if(q[i].empty())
cout<<"无";
while(!q[i].empty()){
int index=q[i].front( );
cout<<index<<" ";
q[i].pop();
}
cout<<endl;
}
}
//判断顶点nodes[j]是否可以涂上颜色color
bool ifOk(Node* nodes,int** graph,int color,int j){
if(nodes[j].color!=0)
return false;
for(int i=0;i<13;i++)
if(graph[nodes[j].index][i]==1)
for(int m=0;m<13;m++)
if(nodes[m].index==i)
if(nodes[m].color==color)
return false;
return true;
}
int main() {
//初始化邻接矩阵
int** graph=new int*[13];
for(int i=0;i<13;i++)
graph[i]=new int[13];
//初始化顶点数组，记录13个顶点的索引、度数、颜色
Node* nodes = new Node[13];
for (int i = 0;i < 13;i++) {
int degree = 0;
for (int j = 0;j < 13;j++) {
cin >> graph[i][j];
if (graph[i][j])
degree++;
}
nodes[i].index = i;
nodes[i].degree = degree;
nodes[i].color = 0;
}
//对顶点按度数递减排序
sort(nodes);
//输出排序后的结果
cout<<"按度数由大到小排序后的结果：";
for(int i=0;i<13;i++){
cout<<nodes[i].index<<" ";
if(i==12)
cout<<endl;
}
output(nodes);
//对13个顶点采用贪婪算法进行迭代涂色
int k = 0;
while (true) {
k++;
int i;
for (i = 0;i < 13;i++)
if (nodes[i].color == 0) {
nodes[i].color = k;
break;
}
if (i == 13)
break;
for (int j = 0;j < 13;j++)
if (ifOk(nodes,graph,k,j))
nodes[j].color = k;
}
//输出所需最小颜色数和一种涂色方案
cout <<"所需要的最小颜色数目："<<k-1<<endl;
cout<<"一种涂色方案为："<<endl;
for(int i=1;i<k;i++){
cout<<i<<':';
for(int j=0;j<13;j++)
if(nodes[j].color==i)
cout<<nodes[j].index<<' ';
if(i<k-1)
cout<<endl;
}
}
编译运行：
$ g++ traffic12.cpp
$ a.out
0 0 0 0 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1 0 0
1 1 0 0 0 0 1 0 0 0 1 1 0
1 1 0 0 0 1 0 0 0 0 1 1 0
0 1 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
按度数由大到小排序后的结果：1 5 6 10 0 11 2 4 7 9 3 8 12
度数为5的顶点：1 5 6 10
度数为4的顶点：0 11
度数为3的顶点：2 4 7 9
度数为2的顶点：无
度数为1的顶点：无
度数为0的顶点：3 8 12
所需要的最小颜色数目：4
一种涂色方案为：
1:1 0 11 3 8 12
2:5 2 4
3:6 7 9
4:10
