C ++程序对完整图形执行边缘着色

完整图是在任意一对顶点之间具有连接边的图。这是一个在完整图形上执行边缘着色的C ++程序。

算法

Begin
    输入顶点数“n”。
    用e=n*(n-1)/2条边构造一个完整的图，在ed[][]中。
    函数EdgeColor()用于为图形边缘着色。
    A） 最初将颜色指定给当前边，即1。
    B） 不相干
    放弃此颜色并再次转到标志并尝试下一种颜色。
    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; //assign color to current edge as c i.e. 1 initially.
      flag:
         ed[i][2] = c;
         //如果任何相邻边都占据相同的颜色，则
         discard this color and go to flag again and try next color.
         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
      n1):"<<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.