对输入图的折线图执行边缘着色的 C++ 程序

Z时代
2024-01-10
分类：综合

无向图 G 的折线图是另一种表示 G 的L(G)边之间的邻接关系的图。在这个程序中，我们对输入图的折线图进行边着色。

算法

Begin

Take the input of the number of vertices ‘n’ and number of edges ‘e’.

Take the input of ‘n’ vertex pairs for the ‘e’ edges in the graph in ed[][]. Function GenLineGraph(): Construct a line graph in LineEd[][].

To construct line graph, for each edge in the given graph, connect it

to its adjacent edge in LineEd.

Function EdgeColor(): Color the graph edges of LineEdge[][] graph.

Assign color to current edge as col i.e. 1 initially.

If any of the adjacent edges have the same color, then discard this

color and go to flag again and try next color.

Print the color for each edge of the line graph.

End.

示例代码

#include<iostream>
using namespace std;
int GenLineGraph(int ed[][2], char LineEd[][3], int e) {
   int i, cnt = 0, j, N;
   char c;
   for(i = 0; i < e; i++) {
      for(j = i+1; j < e; j++) {
         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]) {
            LineEd[cnt][0] = 'a'+i;
            LineEd[cnt][1] = 'a'+j;
            LineEd[cnt][2] = 0;
            cnt++;
         }
      }
   }
   N = cnt;
   cout<<"\n\nThe adjacency list representation for the given graph: ";
   for(i = 0; i < e; i++) {
      cnt = 0;
      c = 'a'+i;
      cout<<"\n\t"<<c<<"-> { ";
      for(j = 0; j < N; j++) {
         if(LineEd[j][0] == i+'a') {
            cout<<LineEd[j][1]<<" ";
            cnt++;
         } else if(LineEd[j][1] == i+'a') {
            cout<<LineEd[j][0]<<" ";
            cnt++;
         } else if(j == e-1 && cnt == 0)
            cout<<"孤立的顶点！";
      }
      cout<<" }";
   }
   return N;
}
void EdgeColor(char ed[][3], int e) {
   int i, col, j;
   for(i = 0; i < e; i++) {
      col = 1;
      flag:
         ed[i][2] = col;
      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]) {
               col++;
               goto flag;
            }
         }
      }
   }
}
int main() {
   int i, n, e, j, max = -1;
   char c= 'a';
   cout<<"输入图形的顶点数： ";
   cin>>n;
   cout<<"输入图形的边数： ";
   cin>>e;
   int ed[e][2];
   char LineEd[e*e][3];
   for(i = 0; i < e; i++) {
      cout<<"\nEnter the vertex pair for edge '"<<c++<<"'";
      cout<<"\nV(1): ";
      cin>>ed[i][0];
      cout<<"V(2): ";
      cin>>ed[i][1];
   }
   e = GenLineGraph(ed, LineEd, e);
   EdgeColor(LineEd , e);
   for(i = 0; i < e; i++)
      cout<<"\nThe color of the edge between vertex n(1):"<<LineEd[i][0]<<" and n(2):"<<LineEd[i][1]<<" is: color"<<0+LineEd[i][2]<<".";
}

输出结果

输入图形的顶点数：4
输入图形的边数： 3
Enter the vertex pair for edge 'a'
V(1): 1
V(2): 2
Enter the vertex pair for edge 'b'
V(1): 3
V(2): 2
Enter the vertex pair for edge 'c'
V(1): 4
V(2): 1
The adjacency list representation for the given graph:
a-> { b c }
b-> { a }
c-> { a }
The color of the edge between vertex n(1):a and n(2):b is: color1.
The color of the edge between vertex n(1):a and n(2):c is: color2.