Chương trình C++ kiểm tra đồ thị hai phía bằng thuật toán 2 màu

Đồ thị hai phía là đồ thị có thể tô màu bằng hai màu. Chương trình này sử dụng thuật toán tô màu 2 màu (backtracking) để kiểm tra.

Các hàm và mã giả

Bắt đầu
  1. Hàm isSafe() kiểm tra việc gán màu cho đỉnh v có an toàn không.
  2. Hàm graphColoringtil(g, k, col, v):
       g[V][V] ma trận kề, k số màu, col[] mảng màu.
       Nếu v == V trả về true.
       Với c = 1 đến k:
           Nếu isSafe(v, g, col, c) thì gán col[v]=c.
           Nếu graphColoringtil(g, k, col, v+1) true thì trả true.
           Khôi phục col[v]=0.
       Trả false.
  3. Hàm graphColoring(g, k): khởi tạo màu, gọi graphColoringtil.
Kết thúc

Ví dụ

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

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

bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
    if (v == V) return true;
    for (int c = 1; c <= k; c++) {
        if (isSafe(v, g, col, c)) {
            col[v] = c;
            if (graphColoringtil(g, k, col, v+1) == true)
                return true;
            col[v] = 0; // backtrack
        }
    }
    return false;
}

Kết quả

The graph is Bipartite