地圖著色演算法

Table of content
上一頁
下一頁

地圖著色問題是指，給定一個圖 G {V, E}，其中 V 和 E 分別是圖的頂點集和邊集，需要對 V 中的所有頂點進行著色，使得任何兩個相鄰的頂點不能具有相同的顏色。

該演算法的現實應用包括：分配移動無線電頻率、制定時間表、設計數獨、分配暫存器等。

地圖著色演算法

使用地圖著色演算法，將圖 G 和要新增到圖中的顏色作為輸入，最終得到一個著色圖，其中任何兩個相鄰頂點都沒有相同的顏色。

演算法

  • 初始化圖中的所有頂點。

  • 選擇度數最高的節點，並用任何顏色對其進行著色。

  • 使用選擇顏色函式選擇要用於圖的顏色，以確保沒有相鄰頂點具有相同的顏色。

  • 檢查是否可以新增顏色，如果可以，則將其新增到解集中。

  • 從步驟 2 重複此過程，直到輸出集準備好。

示例

Map_Colouring_graph

步驟 1

找到所有頂點的度數 -

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

步驟 2

選擇度數最高的頂點首先著色，即 A，並使用選擇顏色函式選擇顏色。檢查顏色是否可以新增到頂點，如果可以，則將其新增到解集中。

highest_degree

步驟 3

從剩餘頂點中選擇任何具有次高度數的頂點，並使用選擇顏色函式對其進行著色。

D 和 E 都有次高度數 3，因此在兩者之間選擇一個，例如 D。

d_highest_degree

D 與 A 相鄰，因此不能與 A 使用相同的顏色。因此，使用選擇顏色函式選擇不同的顏色。

步驟 4

下一個度數最高的頂點是 E，因此選擇 E。

E_highest_degree

E 與 A 和 D 都相鄰，因此不能與 A 和 D 使用相同的顏色。使用選擇顏色函式選擇不同的顏色。

步驟 5

下一個度數最高的頂點是 B 和 C。因此，隨機選擇一個。

B_and_C_highest_degree

B 與 A 和 E 相鄰，因此不允許使用 A 和 E 的顏色，但它與 D 不相鄰，因此可以使用 D 的顏色。

步驟 6

剩下的最後一個頂點是 C，它與 A 和 D 相鄰，不允許使用 A 和 D 的顏色。但它與 E 不相鄰，因此可以使用 E 的顏色。

C_highest_degree

示例

以下是地圖著色演算法在各種程式語言中的完整實現，其中圖的著色方式使得任何兩個相鄰頂點都沒有相同的顏色。

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
列印頁面
上一頁
下一頁
廣告