এই সমস্যায়, একটি অনির্দেশিত গ্রাফ দেওয়া আছে। এছাড়া m রঙ দেওয়া আছে। সমস্যাটি হলো নোডগুলোকে m ভিন্ন রঙ দিয়ে রঙিন করা যেতে পারে কিনা, যাতে গ্রাফের কোনো দুটি আডজাসেন্ট ভার্টেক্স একই রঙের না হয়। যদি সমাধান এক্সিস্ট করে, তবে কোন ভার্টেক্সে কোন রঙ অ্যাসাইন করা হয়েছে সেটি ডিসপ্লে করতে হবে।
ভার্টেক্স ০ থেকে শুরু করে, আমরা এক-এক করে ভিন্ন নোডে রঙ অ্যাসাইন করার চেষ্টা করব। কিন্তু অ্যাসাইন করার আগে, চেক করতে হবে রঙটি সেফ কিনা। একটি রঙ সেফ নয় যদি আডজাসেন্ট ভার্টেক্সগুলো একই রঙ ধারণ করে।
ইনপুট এবং আউটপুট
ইনপুট: একটি গ্রাফ G(V, E)-এর এডজেসেন্সি ম্যাট্রিক্স এবং একটি ইন্টিজার m, যা ইন্ডিকেট করে সর্বোচ্চ কতগুলো রঙ ব্যবহার করা যাবে।ধরা যাক সর্বোচ্চ রঙ m = 3। আউটপুট: এই অ্যালগরিদম রিটার্ন করবে কোন নোডে কোন রঙ অ্যাসাইন করা হয়েছে। যদি সমাধান সম্ভব না হয়, তবে false রিটার্ন করবে। এই ইনপুটের জন্য অ্যাসাইন করা রঙগুলো: Node 0 -> color 1 Node 1 -> color 2 Node 2 -> color 3 Node 3 -> color 2
অ্যালগরিদম
isValid(vertex, colorList, col)
ইনপুট - ভার্টেক্স, চেক করার colorList, এবং col যেটি অ্যাসাইন করার চেষ্টা করা হচ্ছে।
আউটপুট - True যদি রঙ অ্যাসাইন করা বৈধ হয়, অন্যথায় false।
শুরু
গ্রাফের সব ভার্টেক্স v-এর জন্য করুন
যদি v এবং i-এর মধ্যে এজ থাকে, এবং col = colorList[i], তবে
return false
শেষ
return true
শেষ
graphColoring(colors, colorList, vertex)
ইনপুট - সর্বোচ্চ সম্ভাব্য রঙ, কোন ভার্টেক্সে কোন রঙ অ্যাসাইন করা হয়েছে সেটির লিস্ট, এবং শুরুর ভার্টেক্স।
আউটপুট - True, যখন রঙ অ্যাসাইন হয়ে যায়, অন্যথায় false।
শুরু
যদি সব ভার্টেক্স চেক হয়ে যায়, তবে
return true
উপলব্ধ সব রঙ col-এর জন্য করুন
যদি isValid(vertex, color, col), তবে
vertex-এর জন্য colorList-এ col যোগ করুন
যদি graphColoring(colors, colorList, vertex+1) = true, তবে
return true
vertex-এর জন্য রঙ রিমুভ করুন
শেষ
return false
শেষ
উদাহরণ
#include<iostream> #define V 4 using namespace std; bool graph[V][V] = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}, }; void showColors(int color[]) { cout << "Assigned Colors are: " <<endl; for (int i = 0; i < V; i++) cout << color[i] << " "; cout << endl; } bool isValid(int v,int color[], int c) { //চেক করুন v-এর জন্য রঙ c দিয়ে রাখা বৈধ কিনা for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; } bool graphColoring(int colors, int color[], int vertex) { if (vertex == V) //যখন সব ভার্টেক্স বিবেচিত হয়েছে return true; for (int col = 1; col <= colors; col++) { if (isValid(vertex,color, col)) { //চেক করুন col রঙটি বৈধ কিনা color[vertex] = col; if (graphColoring (colors, color, vertex+1) == true) //অতিরিক্ত ভার্টেক্সের জন্য যান return true; color[vertex] = 0; } } return false; //যখন কোনো রঙ অ্যাসাইন করা যায় না } bool checkSolution(int m) { int *color = new int[V]; //প্রতিটি ভার্টেক্সের জন্য কালার ম্যাট্রিক্স বানান for (int i = 0; i < V; i++) color[i] = 0; //প্রাথমিকভাবে ০ সেট করুন if (graphColoring(m, color, 0) == false) { //ভার্টেক্স ০ থেকে গ্রাফ কালারিং চেক করুন cout << "Solution does not exist."; return false; } showColors(color); return true; } int main() { int colors = 3; // রঙের সংখ্যা checkSolution (colors); }
আউটপুট
Assigned Colors are: 1 2 3 2
