Chương trình C++ giải bài toán 4 màu (4-Color Problem)

Bài toán 4 màu phát biểu rằng bất kỳ bản đồ phẳng nào cũng có thể tô màu bằng tối đa 4 màu sao cho không có hai vùng chung đường biên nào cùng màu. Chương trình này sử dụng thuật toán quay lui (backtracking) để tìm cách tô màu hợp lệ.

Thuật toán

Hàm isSafe(v, graph, color, c):
  Kiểm tra xem có đỉnh kề nào đã được tô màu c không.
  Nếu có: trả về false. Ngược lại: true.

Hàm graphColoringUtil(graph, m, color, v):
  Nếu v == V (đã tô hết): trả về true.
  Với mỗi màu c từ 1 đến m:
    Nếu isSafe(v, graph, color, c):
      Gán color[v] = c.
      Nếu graphColoringUtil(graph, m, color, v+1) thành công: trả về true.
      Quay lui: color[v] = 0.
  Trả về false.

Hàm graphColor(graph, m):
  Khởi tạo mảng color[] = 0.
  Gọi graphColoringUtil từ đỉnh 0.
  Nếu thất bại: in "Khong co giai phap".
  Ngược lại: in kết quả.

Ví dụ mã nguồn

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;

bool isSafe(int v, bool graph[V][V], int color[], int c) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
    if (v == V) return true;
    for (int c = 1; c <= m; c++) {
        if (isSafe(v, graph, color, c)) {
            color[v] = c;
            if (graphColoringUtil(graph, m, color, v+1))
                return true;
            color[v] = 0;
        }
    }
    return false;
}

void printSolution(int color[]) {
    cout << "Cac mau da gan:\n";
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
    cout << endl;
}

bool graphColor(bool graph[V][V], int m) {
    int color[V] = {0};
    if (!graphColoringUtil(graph, m, color, 0)) {
        cout << "Khong co giai phap";
        return false;
    }
    printSolution(color);
    return true;
}

int main() {
    bool graph[V][V] = {
        {0, 0, 1, 0, 1},
        {1, 1, 1, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0}
    };
    int m = 4;
    graphColor(graph, m);
    return 0;
}

Đầu ra

Cac mau da gan:
1 2 3 1 1