M色问题
在这个问题中，给出了无向图。还提供m种颜色。问题在于确定是否可以为节点分配m种不同的颜色，以使该图的两个相邻顶点都不具有相同的颜色。如果存在解决方案，则显示在哪个顶点上分配了哪种颜色。
从顶点0开始，我们将尝试将颜色一一分配给不同的节点。但是在分配之前，我们必须检查颜色是否安全。如果相邻的顶点包含相同的颜色，则该颜色是不安全的。
输入输出
Input: The adjacency matrix of a graph G(V, E) and an integer m, which indicates the maximum number of colors that can be used.Let the maximum color m = 3. Output: This algorithm will return which node will be assigned with which color. If the solution is not possible, it will return false. For this input the assigned colors are: Node 0 -> color 1 Node 1 -> color 2 Node 2 -> color 3 Node 3 -> color 2
算法
isValid（顶点，colorList，col）
输入- 顶点，要检查的colorList和要分配的颜色。
输出-如果颜色分配有效，则为true，否则为false。
Begin
for all vertices v of the graph, do
if there is an edge between v and i, and col = colorList[i], then
return false
done
return true
EndgraphColoring（颜色，colorList，顶点）
输入- 尽可能多的颜色，顶点用哪种颜色上色的列表以及起始顶点。
输出-分配颜色时为True，否则为false。
Begin
if all vertices are checked, then
return true
for all colors col from available colors, do
if isValid(vertex, color, col), then
add col to the colorList for vertex
if graphColoring(colors, colorList, vertex+1) = true, then
return true
remove color for vertex
done
return false
End示例
#include<iostream>
#define V 4
using namespace std;
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0},
};
void showColors(int color[]) {
cout << "Assigned Colors are: " <<endl;
for (int i = 0; i < V; i++)
cout << color[i] << " ";
cout << endl;
}
bool isValid(int v,int color[], int c) { //check whether putting a color valid for v
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
bool graphColoring(int colors, int color[], int vertex) {
if (vertex == V) //when all vertices are considered
return true;
for (int col = 1; col <= colors; col++) {
if (isValid(vertex,color, col)) { //check whether color col is valid or not
color[vertex] = col;
if (graphColoring (colors, color, vertex+1) == true) //go for additional vertices
return true;
color[vertex] = 0;
}
}
return false; //when no colors can be assigned
}
bool checkSolution(int m) {
int *color = new int[V]; //make color matrix for each vertex
for (int i = 0; i < V; i++)
color[i] = 0; //initially set to 0
if (graphColoring(m, color, 0) == false) { //for vertex 0 check graph coloring
cout << "解决方案不存在。";
return false;
}
showColors(color);
return true;
}
int main() {
int colors = 3; // Number of colors
checkSolution (colors);
}输出结果
Assigned Colors are: 1 2 3 2