यहां ग्रीडी कलरिंग परफॉर्म करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम:
Begin वर्टेक्स और एज की संख्या को इनपुट के रूप में लें। greedyColoring() फंक्शन बनाएं वर्टेक्स को रंग असाइन करने के लिए: A) पहले वर्टेक्स को पहला रंग असाइन करें। B) शेष वर्टेक्स को इनिशियलाइज़ करें। C) उपलब्ध रंगों को संग्रहीत करने के लिए एक अस्थायी ऐरे घोषित करें। D) शेष वर्टेक्स को रंग असाइन करें। समाधान प्रिंट करें। End
उदाहरण कोड
#include<bits/stdc++.h> #include<iostream> using namespace std; int n,e,i,j; vector<vector<int> > g; vector<int> col; bool visit[1001]; void greedyColoring() { col[0] = 0; for (i=1;i<n;i++) col[i] = -1; bool unuse[n]; for (i=0;i<n;i++) unuse[i]=0; for (i = 1; i < n; i++) { for (j=0;j<g[i].size();j++) if (col[g[i][j]] != -1) unuse[col[g[i][j]]] = true; int cr; for (cr=0;cr<n;cr++) if (unuse[cr] == false) break; col[i] = cr; for (j=0;j<g[i].size();j++) if (col[g[i][j]] != -1) unuse[col[g[i][j]]] = false; } } int main() { int a,b; cout<<"Enter number of vertices and edges respectively:"; cin>>n>>e; cout<<"\n"; g.resize(n); col.resize(n); memset(visit,0,sizeof(visit)); for(i=0;i<e;i++) { cout<<"\nEnter edge vertices of edge "<<i+1<<" :"; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } greedyColoring(); for(i=0;i<n;i++) { cout<<"Vertex "<<i+1<<" is coloured with "<<col[i]+1<<"\n"; } }
आउटपुट
Enter number of vertices and edges respectively:7 6 Enter edge vertices of edge 1 :4 5 Enter edge vertices of edge 2 :2 3 Enter edge vertices of edge 3 :1 1 Enter edge vertices of edge 4 :1 4 Enter edge vertices of edge 5 :6 7 Enter edge vertices of edge 6 :2 2 Vertex 1 is coloured with 1 Vertex 2 is coloured with 1 Vertex 3 is coloured with 2 Vertex 4 is coloured with 2 Vertex 5 is coloured with 1 Vertex 6 is coloured with 1 Vertex 7 is coloured with 2
