Chương trình C ++ để thực hiện tô màu cạnh của đồ thị

Trong chương trình này, chúng ta sẽ thực hiện Tô màu cho các cạnh của một đồ thị, trong đó chúng ta phải tô màu các cạnh của đồ thị mà không có hai cạnh liền kề nào có cùng màu.

Thuật toán

Begin
   Take the input of the number of vertices, n, and then number of edges, e, in the graph.
   The graph is stored as adjacency list.
   BFS is implemented using queue and colors are assigned to each edge.
End

Ví dụ

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
   queue<int> q;
   int c = 0;
   set<int> vertex_colored;
   if(v[n])
      return;
      v[n] = 1;
   for(i = 0;i<g[n].size();i++) {
      if(color[g[n][i].second]!=-1) {
         vertex_colored.insert(color[g[n][i].second]);
      }
   }
   for(i = 0;i<g[n].size();i++) {
      if(!v[g[n][i].first]) {
         q.push(g[n][i].first);
      }
      if(color[g[n][i].second]==-1) {
         while(vertex_colored.find(c)!=vertex_colored.end())
            c++;
            color[g[n][i].second] = c;
            vertex_colored.insert(c);
            c++;
      }
   }
   while(!q.empty()) {
      int temp = q.front();
      q.pop();
      col(temp);
   }
   return;
}
int main() {
   int u,w;
   set<int> empty;
   cout<<"Enter number of vertices and edges respectively:";
   cin>>n>>e;
   cout<<"\n";
   g.resize(n); //number of vertices
   color.resize(e,-1); //number of edges
   memset(v,0,sizeof(v));
   for(i = 0;i<e;i++) {
      cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
      cin>>u>>w;
      u--; w--;
      g[u].push_back(make_pair(w,i));
      g[w].push_back(make_pair(u,i));
   }
   col(0);
   for(i = 0;i<e;i++) {
      cout<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
      << "\n";
   }
}

Đầu ra

Enter number of vertices and edges respectively:4 5
Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :2 3
Enter edge vertices of edge 3 :1 1
Enter edge vertices of edge 4 :3 4
Enter edge vertices of edge 5 :1 4
Edge 1 is coloured with colour 1
Edge 2 is coloured with colour 2
Edge 3 is coloured with colour 2
Edge 4 is coloured with colour 1
Edge 5 is coloured with colour 3