M 着色问题
什么是 M 着色问题？
在M 着色问题中，我们的任务是确定是否有可能为给定图的节点分配 m 种不同的颜色，使得图中任何两个相邻顶点的颜色都不相同。如果存在解，则显示每个顶点分配的颜色。 m-着色问题实际上用于解决聚类、调度、作业分配等问题。
图是一种抽象数据类型 (ADT)，由一组通过链接连接的对象组成。
输入输出场景
假设给定的无向图 G(V, E) 及其邻接矩阵如下 −
设最大颜色数 m = 3，表示可以使用的最大颜色数。回溯算法可用于解决上述图的 m-着色问题。该算法将返回哪个节点将被分配哪种颜色。如果无法找到解决方案，则返回 false。
在这种情况下，输出应为节点 0 -> 颜色 1，节点 1 -> 颜色 2，节点 2 -> 颜色 3，节点 3 -> 颜色 2。下图演示了相同的 −
使用回溯法解决 M-Coloring 问题
解决 m-Coloring 问题的简单方法是生成所有可能的顶点与颜色组合，并检查是否有任何组合满足给定的约束。然而，对于较大的图，这种方法效率低下。
要使用回溯法解决 m 着色问题，请按照以下步骤 −
从顶点 0 开始，我们将尝试逐一为不同的节点分配颜色。
但是，在分配颜色之前，我们必须检查颜色是否安全。当相邻顶点包含相同的颜色时，颜色是不安全的。
接下来，我们将检查是否存在满足约束条件的颜色分配。如果满足，我们将该颜色分配标记为 m 着色问题的解。
示例
在下面的示例中，我们将说明如何在给定的无向图中解决 m 着色问题。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define V 4
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
void showColors(int color[]) {
printf("Assigned Colors are:
");
for (int i = 0; i < V; i++)
printf("%d ", color[i]);
printf("
");
}
//检查颜色是否对v有效
bool isValid(int v, int color[], int c) {
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)
return true;
for (int col = 1; col <= colors; col++) {
//检查颜色是否有效
if (isValid(vertex, color, col)) {
color[vertex] = col;
// 寻找额外的顶点
if (graphColoring(colors, color, vertex + 1))
return true;
color[vertex] = 0;
}
}
//当无法分配颜色时
return false;
}
bool checkSolution(int m) {
//为每个顶点制作颜色矩阵
int *color = (int *)malloc(V * sizeof(int));
for (int i = 0; i < V; i++)
//初始设置为 0
color[i] = 0;
//对于顶点 0 检查图形着色
if (graphColoring(m, color, 0) == false) {
printf("Solution does not exist.
");
free(color);
return false;
}
showColors(color);
free(color);
return true;
}
int main() {
// 颜色数量
int colors = 3;
checkSolution(colors);
return 0;
}
#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;
}
//检查颜色是否对v有效
bool isValid(int v,int color[], int c) {
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)
return true;
for (int col = 1; col <= colors; col++) {
//检查颜色是否有效
if (isValid(vertex,color, col)) {
color[vertex] = col;
// 寻找额外的顶点
if (graphColoring (colors, color, vertex+1) == true)
return true;
color[vertex] = 0;
}
}
//当无法分配颜色时
return false;
}
bool checkSolution(int m) {
//为每个顶点制作颜色矩阵
int *color = new int[V];
for (int i = 0; i < V; i++)
//初始设置为 0
color[i] = 0;
//对于顶点 0 检查图形着色
if (graphColoring(m, color, 0) == false) {
cout << "Solution does not exist.";
return false;
}
showColors(color);
return true;
}
int main() {
// 颜色数量
int colors = 3;
checkSolution (colors);
}
public class GraphColoring {
static final int V = 4;
static boolean[][] graph = {
{false, true, true, true},
{true, false, true, false},
{true, true, false, true},
{true, false, true, false}
};
static void showColors(int[] color) {
System.out.println("Assigned Colors are:");
for (int i = 0; i < V; i++) {
System.out.print(color[i] + " ");
}
System.out.println();
}
//检查颜色是否对v有效
static boolean isValid(int v, int[] color, int c) {
for (int i = 0; i < V; i++) {
if (graph[v][i] && c == color[i]) {
return false;
}
}
return true;
}
static boolean graphColoring(int colors, int[] color, int vertex) {
//当考虑所有顶点时
if (vertex == V) {
return true;
}
for (int col = 1; col <= colors; col++) {
//检查颜色是否有效
if (isValid(vertex, color, col)) {
color[vertex] = col;
// 寻找额外的顶点
if (graphColoring(colors, color, vertex + 1)) {
return true;
}
color[vertex] = 0;
}
}
//当无法分配颜色时
return false;
}
static boolean checkSolution(int m) {
//为每个顶点制作颜色矩阵
int[] color = new int[V];
for (int i = 0; i < V; i++) {
//初始设置为 0
color[i] = 0;
}
//对于顶点 0 检查图形着色
if (!graphColoring(m, color, 0)) {
System.out.println("Solution does not exist.");
return false;
}
showColors(color);
return true;
}
public static void main(String[] args) {
// 颜色数量
int colors = 3;
checkSolution(colors);
}
}
V = 4
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
def show_colors(color):
print("Assigned Colors are:")
for i in range(V):
print(color[i], end=" ")
print()
def is_valid(v, color, c):
for i in range(V):
if graph[v][i] and c == color[i]:
return False
return True
def graph_coloring(colors, color, vertex):
if vertex == V:
return True
for col in range(1, colors + 1):
if is_valid(vertex, color, col):
color[vertex] = col
if graph_coloring(colors, color, vertex + 1):
return True
color[vertex] = 0
return False
def check_solution(m):
color = [0] * V
if not graph_coloring(m, color, 0):
print("Solution does not exist.")
return False
show_colors(color)
return True
if __name__ == "__main__":
colors = 3
check_solution(colors)
输出
Assigned Colors are: 1 2 3 2
