地图着色算法

地图着色问题指出，给定图 G {V，E}，其中 V 和 E 是图的顶点和边的集合，V 中的所有顶点都需要以这样的方式着色，即没有两个相邻顶点必须具有相同的颜色。

该算法的实际应用是——分配移动无线电频率、制定时间表、设计数独、分配寄存器等。

地图着色算法

通过地图着色算法，以图G和要添加到图中的颜色作为输入，得到不存在两个相邻顶点具有相同颜色的着色图。

算法

初始化图中的所有顶点。
选择度数最高的节点，用任意颜色为其着色。
借助选择颜色函数选择图形上要使用的颜色，以便相邻顶点不具有相同的颜色。
检查是否可以添加颜色，如果可以，请将其添加到解决方案集中。
重复步骤 2 开始的过程，直到输出集准备就绪。

例子

步骤1

求所有顶点的度数 -

A – 4
B – 2
C – 2
D – 3
E – 3

第2步

首先选择度数最高的顶点，即A，并使用选择颜色函数选择颜色。检查颜色是否可以添加到顶点，如果可以，则将其添加到解集。

步骤3

从剩余顶点中选择具有下一个最高度数的任何顶点，并使用选择颜色函数对其进行着色。

D 和 E 都具有次高的度数 3，因此选择它们之间的任何一个，例如 D。

D 与 A 相邻，因此不能使用与 A 相同的颜色。因此，请使用选择颜色功能选择不同的颜色。

步骤4

下一个最高度数的顶点是 E，因此选择 E。

E 与 A 和 D 相邻，因此不能使用与 A 和 D 相同的颜色。使用选择颜色功能选择不同的颜色。

步骤5

下一个最高度数的顶点是 B 和 C。因此，随机选择任意一个。

B 与 A 和 E 都相邻，因此不允许用 A 和 E 的颜色着色，但它不与 D 相邻，因此可以用 D 的颜色着色。

步骤6

剩下的下一个也是最后一个顶点是 C，它与 A 和 D 都相邻，不允许使用 A 和 D 的颜色对它进行着色。但它与 E 不相邻，因此可以用 E 的颜色对它进行着色。

例子

以下是地图着色算法在各种编程语言中的完整实现，其中图的着色方式使得没有两个相邻顶点具有相同的颜色。

C C++ Java Python

#include<stdio.h>
#include<stdbool.h>
#define V 4
bool graph[V][V] = {
   {0, 1, 1, 0},
   {1, 0, 1, 1},
   {1, 1, 0, 1},
   {0, 1, 1, 0},
};
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 mColoring(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 (mColoring (colors, color, vertex+1) == true) //go for additional vertices
            return true;
         color[vertex] = 0;
      }
   }
   return false; //when no colors can be assigned
}
int main(){
   int colors = 3; // Number of colors
   int color[V]; //make color matrix for each vertex
   for (int i = 0; i < V; i++)
      color[i] = 0; //initially set to 0
   if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
      printf("Solution does not exist.");
   }
   printf("Assigned Colors are: \n");
   for (int i = 0; i < V; i++)
      printf("%d ", color[i]);
   return 0;
}

输出

Assigned Colors are:
1 2 3 1

#include<iostream>
using namespace std;
#define V 4
bool graph[V][V] = {
   {0, 1, 1, 0},
   {1, 0, 1, 1},
   {1, 1, 0, 1},
   {0, 1, 1, 0},
};
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 mColoring(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 (mColoring (colors, color, vertex+1) == true) //go for additional vertices
            return true;
         color[vertex] = 0;
      }
   }
   return false; //when no colors can be assigned
}
int main(){
   int colors = 3; // Number of colors
   int color[V]; //make color matrix for each vertex
   for (int i = 0; i < V; i++)
      color[i] = 0; //initially set to 0
   if (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
      cout << "Solution does not exist.";
   }
   cout << "Assigned Colors are: \n";
   for (int i = 0; i < V; i++)
      cout << color[i] << " ";
   return 0;
}

输出

Assigned Colors are: 
1 2 3 1

public class mcolouring {
   static int V = 4;
   static int graph[][] = {
      {0, 1, 1, 0},
      {1, 0, 1, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 0},
   };
   static boolean 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] != 0 && c == color[i])
            return false;
      return true;
   }
   static boolean mColoring(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 (mColoring (colors, color, vertex+1) == true) //go for additional vertices
               return true;
            color[vertex] = 0;
         }
      }
      return false; //when no colors can be assigned
   }
   public static void main(String args[]) {
      int colors = 3; // Number of colors
      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 (mColoring(colors, color, 0) == false) { //for vertex 0 check graph coloring
         System.out.println("Solution does not exist.");
      }
      System.out.println("Assigned Colors are: \n");
      for (int i = 0; i < V; i++)
         System.out.print(color[i] + " ");
   }
}

输出

Assigned Colors are:
1 2 3 1

V = 4
graph = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
def isValid(v, color, c):  # check whether putting a color valid for v
    for i in range(V):
        if graph[v][i] and c == color[i]:
            return False
    return True
def mColoring(colors, color, vertex):
    if vertex == V:  # when all vertices are considered
        return True
    for col in range(1, colors + 1):
        if isValid(vertex, color,
                   col):  # check whether color col is valid or not
            color[vertex] = col
            if mColoring(colors, color, vertex + 1):
                return True  # go for additional vertices
            color[vertex] = 0
    return False  # when no colors can be assigned
colors = 3  # Number of colors
color = [0] * V  # make color matrix for each vertex
if not mColoring(
        colors, color,
        0):  # initially set to 0 and for Vertex 0 check graph coloring
    print("Solution does not exist.")
else:
    print("Assigned Colors are:")
    for i in range(V):
        print(color[i], end=" ")

输出

Assigned Colors are:
1 2 3 1