โปรแกรม C++ เพื่อทำการระบายสีขอบให้กับกราฟเส้นของกราฟอินพุต

กราฟเส้นของกราฟ G แบบไม่บอกทิศทาง เป็นอีกกราฟ L(G) ที่แสดงความชิดระหว่างขอบของ 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<<"Isolated Vertex!";
      }
      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<<"Enter the number of vertices of the graph: ";
   cin>>n;
   cout<<"Enter the number of edges of the graph: ";
   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]<<".";
}

ผลลัพธ์

Enter the number of vertices of the graph:4
Enter the number of edges of the graph: 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.