Chương trình C++ tô màu cạnh (Edge Coloring) trên đồ thị hoàn chỉnh

Đồ thị hoàn chỉnh (complete graph) là đồ thị có cạnh nối giữa mọi cặp đỉnh. Đây là chương trình C++ thực hiện tô màu cạnh trên đồ thị hoàn chỉnh.

Thuật toán

Bắt đầu
  Nhập số đỉnh 'n'.
  Xây dựng đồ thị hoàn chỉnh với e = n*(n-1)/2 cạnh, lưu trong ed[][].
  Hàm EdgeColor() tô màu các cạnh:
    A) Gán màu cho cạnh hiện tại là c (ban đầu = 1).
    B) Nếu cùng màu bị chiếm bởi cạnh kề nào, loại bỏ màu đó, quay lại flag thử màu tiếp.
    C) In màu cho mỗi cạnh.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void EdgeColor(int ed[][3], int e) {
    int i, c, j;
    for (i = 0; i < e; i++) {
        c = 1; // gán màu ban đầu = 1
        flag:
        ed[i][2] = c;
        // nếu cùng màu bị cạnh kề chiếm, thử màu khác
        for (j = 0; j < e; j++) {
            if (j == i)
                continue;
            if (ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] ||
                ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                if (ed[j][2] == ed[i][2]) {
                    c++;
                    goto flag;
                }
            }
        }
    }
}

int main() {
    int i, n, e, j, cnt = 0;
    cout << "Nhập số đỉnh cho đồ thị hoàn chỉnh: ";
    cin >> n;
    e = (n * (n - 1)) / 2;
    int ed[e][3];
    for (i = 1; i <= n; i++) {
        for (j = i + 1; j <= n; j++) {
            ed[cnt][0] = i;
            ed[cnt][1] = j;
            ed[cnt][2] = -1;
            cnt++;
        }
    }
    EdgeColor(ed, e);
    for (i = 0; i < e; i++)
        cout << "\nMàu cạnh giữa đỉnh n(1):" << ed[i][0] << " và n(2):" << ed[i][1] << " là: color" << ed[i][2] << ".";
}

Kết quả

Nhập số đỉnh cho đồ thị hoàn chỉnh: 4
Màu cạnh giữa đỉnh n(1):1 và n(2):2 là: color1.
Màu cạnh giữa đỉnh n(1):1 và n(2):3 là: color2.
Màu cạnh giữa đỉnh n(1):1 và n(2):4 là: color3.
Màu cạnh giữa đỉnh n(1):2 và n(2):3 là: color3.
Màu cạnh giữa đỉnh n(1):2 và n(2):4 là: color2.
Màu cạnh giữa đỉnh n(1):3 và n(2):4 là: color1.