C++ প্রোগ্রাম: ৪-কালার সমস্যা বাস্তবায়ন

এটি একটি C++ প্রোগ্রাম যা ৪-কালার সমস্যা বাস্তবায়ন করে।

অ্যালগরিদম

শুরু
  ফাংশন issafe() বিকাশ করুন যাতে বর্তমান রং অ্যাসাইনমেন্ট 
  ভার্টেক্স v-এর জন্য নিরাপদ কিনা চেক করা যায় অর্থাৎ এজ আছে কিনা।
  যদি থাকে,
    তবে চেক করুন যে নতুন ভার্টেক্সে ভরা রং এর সন্নিহিত ভার্টেক্সগুলোর দ্বারা ইতিমধ্যে ব্যবহার করা হয়েছে কিনা।
শেষ
শুরু
  ফাংশন graphColoringtil(bool graph[V][V], int m, int col[], int v)
  ৪ কালারিং সমস্যা সমাধান করুন:
  এখানে,
  g[V][V] = এটি একটি ২D অ্যারে যেখানে V হল গ্রাফের ভার্টেক্স সংখ্যা
  m = ব্যবহৃত হতে পারা সর্বোচ্চ রংের সংখ্যা।
  col[] = একটি রং অ্যারে যাতে ১ থেকে m পর্যন্ত সংখ্যা থাকবে।
  যদি v == V
    true রিটার্ন করুন
  c = 1 থেকে m পর্যন্ত
    যদি (isSafe(v, g, col, c))
      col[v] = c
      যদি (graphColoringtil(g, k, col, v+1) == true)
        true রিটার্ন করুন
      col[v] = 0
  false রিটার্ন করুন
শেষ
শুরু
  ফাংশন graphColor():
    এটি মূলত graphColoringUtil() ব্যবহার করে সমস্যা সমাধান করে।
    যদি m রং অ্যাসাইন করা না যায় তবে false রিটার্ন করুন,
    অন্যথায় true রিটার্ন করুন।
শেষ

উদাহরণ

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;

bool isSafe(int v, bool graph[V][V], int col[], int C) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && C == col[i])
            return false;
    return true;
}

bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
    if (v == V) // যদি সব ভার্টেক্সে রং অ্যাসাইন হয়ে যায়
        return true;
    for (int c = 1; c <= k; c++) { // এই ভার্টেক্স v-কে বিবেচনা করে বিভিন্ন রং চেষ্টা করুন
        if (isSafe(v, g, col, c)) { // চেক করুন রং c v-র জন্য ঠিক কিনা
            col[v] = c;
            if (graphColoringtil(g, k, col, v+1) == true) // বাকি ভার্টেক্সগুলোর রং অ্যাসাইন করার জন্য রিকার্স
                return true;
            col[v] = 0; // যদি রং c সমাধান না দেয় তবে এটাকে সরিয়ে দিন
        }
    }
    return false;
}

void solution(int color[]) {
    cout << "The assigned colors are: \n";
    for (int i = 0; i < V; i++)
        cout << color[i];
    cout << "\n";
}

bool graphColor(bool graph[V][V], int k) {
    int* color = new int[V];
    // সব রংের মান ০ হিসেবে ইনিশিয়ালাইজ করুন
    for (int i = 0; i < V; i++)
        color[i] = 0;
    if (graphColoringtil(graph, k, color, 0) == false) {
        cout << "Solution does not exist";
        return false;
    }
    solution(color);
    return true;
}

int main() {
    bool g[V][V] = {
        {0, 0, 1, 0, 1},
        {1, 1, 1, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 0, 0}
    };
    int k = 4;
    graphColor(g, k);
    return 0;
}

আউটপুট

The assigned colors are: 1 2 3 1 1