地图着色算法

Table of content

地图着色算法
示例

地图着色问题是指，给定一个图 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: ");
      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

打印页面