इस प्रोग्राम में, हम ग्राफ की एज कलरिंग करेंगे जिसमें हमें ग्राफ के एज को कलर करना है कि कोई दो आसन्न एज का एक ही कलर न हो। उदाहरण में चरण।
एल्गोरिदम
Begin वर्टेक्स की संख्या n, और फिर ग्राफ में एज की संख्या e का इनपुट लें। ग्राफ को एडजेसेंसी लिस्ट के रूप में संग्रहीत किया जाता है। क्यू का उपयोग करके BFS इम्प्लीमेंट किया जाता है और प्रत्येक एज को कलर असाइन किए जाते हैं। End
उदाहरण
#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); //वर्टेक्स की संख्या color.resize(e,-1); //एज की संख्या 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"; } }
आउटपुट
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
