এখানে গ্রিডি কলারিং (Greedy Coloring) বাস্তবায়ন করার একটি সি++ প্রোগ্রাম দেওয়া হলো।
অ্যালগরিদম:
শুরু ভের্টেক্স এবং এজের সংখ্যা ইনপুট নিন। greedyColoring() ফাংশন তৈরি করুন ভের্টেক্সে রঙ অ্যাসাইন করতে: ক) প্রথম ভের্টেক্সকে প্রথম রঙ দিন। খ) বাকি ভের্টেক্সগুলো ইনিশিয়ালাইজ করুন। গ) উপলব্ধ রঙ সংরক্ষণ করার জন্য একটি টেম্পোরারি অ্যারে ডিক্লেয়ার করুন। ঘ) বাকি ভের্টেক্সগুলোকে রঙ দিন। সমাধান প্রিন্ট করুন। শেষ
উদাহরণ কোড
#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<<"ভের্টেক্স এবং এজের সংখ্যা যথাক্রমে লিখুন:"; cin>>n>>e; cout<<"\n"; g.resize(n); col.resize(n); memset(visit,0,sizeof(visit)); for(i=0;i<e;i++) { cout<<"\nএজ নম্বর "<<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"; } }
আউটপুট
ভের্টেক্স এবং এজের সংখ্যা যথাক্রমে লিখুন: ৭ ৬ এজ নম্বর ১-এর এজ ভের্টেক্স লিখুন : 4 5 এজ নম্বর ২-এর এজ ভের্টেক্স লিখুন : 2 3 এজ নম্বর ৩-এর এজ ভের্টেক্স লিখুন : 1 1 এজ নম্বর ৪-এর এজ ভের্টেক্স লিখুন : 1 4 এজ নম্বর ৫-এর এজ ভের্টেক্স লিখুন : 6 7 এজ নম্বর ৬-এর এজ ভের্টেক্স লিখুন : 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
