완전한 그래프에서 에지 채색을 수행하는 C++ 프로그램

완전한 그래프는 정점 쌍 사이에 연결 모서리가 있는 그래프입니다. 이것은 완전한 그래프에 Edge Colouring을 수행하는 C++ 프로그램입니다.

알고리즘

Begin
   Take the input of the number of vertices ‘n’.
   Construct a complete graph using e=n*(n-1)/2 edges, in ed[][].
   Function EdgeColor() is used to Color the graph edges.
   A) Assign color to current edge as c i.e. 1 initially.
   B) If the same color is occupied by any of the adjacent edges, then
      discard this color and go to flag again and try next color.
   C) Print the color for each edge.
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;
         //If the same color is occupied by any of the adjacent edges, then
         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.