โปรแกรม C++ ทำ Edge Coloring บน Complete Graph

Complete graph คือกราฟที่มีขอบเชื่อมระหว่างคู่โหนดใดๆ นี่คือโปรแกรม C++ ทำ Edge Coloring บน Complete Graph

อัลกอริทึม

Begin
  รับจำนวนโหนด 'n'
  สร้าง complete graph โดยใช้ e = n*(n-1)/2 ขอบ ใน ed[][]
  Function EdgeColor() ใช้ระบายสีขอบกราฟ
    A) กำหนดสีให้ขอบปัจจุบันเป็น c คือ 1 เริ่มต้น
    B) ถ้าสีเดียวกันถูกใช้โดยขอบที่อยู่ติดกัน ตัดสีนี้ออก และไป flag อีกครั้ง ลองสีถัดไป
    C) พิมพ์สีสำหรับแต่ละขอบ
End

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void EdgeColor(int ed[][3], int e) {
  int i, c, j;
  for (i = 0; i < e; i++) {
    c = 1;
    flag:
    ed[i][2] = 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 << "Enter the number of vertexes for the complete graph: ";
  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 << "\nThe color of the edge between vertex n(1):" << ed[i][0] << " and n(2):" << ed[i][1] << " is: color" << ed[i][2] << ".";
}

ผลลัพธ์

Enter the number of vertexes for the complete graph: 4
The color of the edge between vertex n(1):1 and n(2):2 is: color1.
The color of the edge between vertex n(1):1 and n(2):3 is: color2.
The color of the edge between vertex n(1):1 and n(2):4 is: color3.
The color of the edge between vertex n(1):2 and n(2):3 is: color3.
The color of the edge between vertex n(1):2 and n(2):4 is: color2.
The color of the edge between vertex n(1):3 and n(2):4 is: color1.