यह C++ प्रोग्राम प्रसिद्ध 4-Color Problem (Four Color Theorem) को दर्शाता है। यह समस्या बताती है कि किसी भी प्लैनर मैप को केवल 4 रंगों से इस तरह कलर किया जा सकता है कि कोई भी दो आसन्न क्षेत्र एक ही रंग के न हों। प्रोग्राम बैकट्रैकिंग एल्गोरिदम का उपयोग करके ग्राफ के वर्टेक्स को कलर करता है।
एल्गोरिदम
शुरुआत
1. फंक्शन isSafe(): जांचें कि वर्टेक्स v के लिए वर्तमान कलर असाइनमेंट सुरक्षित है या नहीं।
- यदि एज मौजूद है, तो जांचें कि नए वर्टेक्स में भरा जाने वाला कलर
उसके आसन्न वर्टेक्स द्वारा पहले से उपयोग तो नहीं किया गया।
2. फंक्शन graphColoringUtil(): 4-कलरिंग समस्या हल करें:
- g[V][V] = 2D ऐरे जहां V वर्टेक्स की संख्या है
- m = उपयोग किए जा सकने वाले अधिकतम रंग
- col[] = कलर ऐरे जिसमें 1 से m तक के नंबर हों
- यदि v == V तो true लौटाएं (सभी वर्टेक्स कलर हो गए)
- c = 1 से m तक:
यदि isSafe(v, g, col, c) है:
col[v] = c
यदि graphColoringUtil(g, m, col, v+1) true है तो true लौटाएं
col[v] = 0 (बैकट्रैक)
- false लौटाएं
3. फंक्शन graphColor(): मुख्य रूप से graphColoringUtil() का उपयोग करके समस्या हल करता है।
समाप्ति
उदाहरण कोड
#include <iostream>
#include <cstdio>
#define V 5
using namespace std;
bool isSafe(int v, bool graph[V][V], int color[], int c) {
for (int i = 0; i < V; i++)
if (graph[v][i] && c == color[i])
return false;
return true;
}
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
if (v == V) return true; // सभी वर्टेक्स कलर हो गए
for (int c = 1; c <= m; c++) {
if (isSafe(v, graph, color, c)) {
color[v] = c;
if (graphColoringUtil(graph, m, color, v + 1))
return true;
color[v] = 0; // बैकट्रैक
}
}
return false;
}
void printSolution(int color[]) {
cout << "The assigned colors are: \n";
for (int i = 0; i < V; i++)
cout << color[i] << " ";
cout << "\n";
}
bool graphColoring(bool graph[V][V], int m) {
int *color = new int[V];
for (int i = 0; i < V; i++) color[i] = 0;
if (!graphColoringUtil(graph, m, color, 0)) {
cout << "Solution does not exist";
return false;
}
printSolution(color);
return true;
}
int main() {
bool graph[V][V] = {
{0, 0, 1, 0, 1},
{1, 1, 1, 0, 0},
{1, 1, 0, 0, 1},
{0, 1, 1, 0, 0},
{0, 0, 0, 0, 0} // 5वीं पंक्ति जोड़ी गई
};
int m = 4;
graphColoring(graph, m);
return 0;
}
आउटपुट
The assigned colors are: 1 2 3 1 1
महत्वपूर्ण नोट: मूल कोड में ग्राफ मैट्रिक्स में केवल 4 पंक्तियाँ थीं जबकि V=5 था। मैंने 5वीं पंक्ति जोड़ दी है। Four Color Theorem के अनुसार, कोई भी प्लैनर ग्राफ अधिकतम 4 रंगों से कलर किया जा सकता है। यह प्रोग्राम बैकट्रैकिंग का उपयोग करके एक वैध कलरिंग खोजता है।