โปรแกรม C++ หา Chromatic Index ของ Cyclic Graphs

Chromatic index คือจำนวนสีสูงสุดที่ต้องใช้สำหรับ edge coloring ของกราฟที่กำหนด นี่คือโปรแกรม C++ หา Chromatic Index ของ Cyclic Graphs

อัลกอริทึม

Begin
  รับจำนวนโหนด 'n' และจำนวนขอบ 'e'
  รับ 'e' คู่โหนดสำหรับ 'e' ขอบใน edge[][]
  Function ChromaticIndex() ระบายสีขอบกราฟ:
    A) กำหนดสีให้ขอบปัจจุบันเป็น c
    B) ถ้าขอบที่อยู่ติดกันมีสีเดียวกัน ตัดสีนี้ออก และไป flag อีกครั้ง ลองสีถัดไป
    C) พิมพ์ chromatic index ของ cyclic graph
    พิมพ์สีของแต่ละขอบ
End

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

#include <iostream>
using namespace std;

int ChromaticIndex(int ed[][3], int e) {
  int i, c, j, max = -1;
  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;
        }
      }
    }
  }
  for (i = 0; i < e; i++) {
    if (max < ed[i][2])
      max = ed[i][2];
  }
  return max;
}

int main() {
  int i, v, e, j, max = -1;
  cout << "Enter the number of vertices of the graph: ";
  cin >> v;
  cout << "Enter the number of edges of the graph: ";
  cin >> e;
  int ed[e][3];
  for (i = 0; i < e; i++) {
    cout << "\nEnter the vertex pair for edge " << i + 1;
    cout << "\nV(1): ";
    cin >> ed[i][0];
    cout << "V(2): ";
    cin >> ed[i][1];
    ed[i][2] = -1;
  }
  cout << "\n\nThe chromatic index of the given graph is: " << ChromaticIndex(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] << ".";
  return 0;
}

ผลลัพธ์

Enter the number of vertices of the graph: 4
Enter the number of edges of the graph: 5
Enter the vertex pair for edge 1
V(1): 2
V(2): 1
Enter the vertex pair for edge 2
V(1): 3
V(2): 2
Enter the vertex pair for edge 3
V(1): 3
V(2): 1
Enter the vertex pair for edge 4
V(1): 4
V(2): 2
Enter the vertex pair for edge 5
V(1): 1
V(2): 3
The chromatic index of the given graph is: 4
The color of the edge between vertex n(1):2 and n(2):1 is: color1.
The color of the edge between vertex n(1):3 and n(2):2 is: color2.
The color of the edge between vertex n(1):3 and n(2):1 is: color3.
The color of the edge between vertex n(1):4 and n(2):2 is: color3.
The color of the edge between vertex n(1):1 and n(2):3 is: color4.