एक बाइपार्टाइट ग्राफ वह ग्राफ है जिसमें ग्राफ कलरिंग दो रंगों का उपयोग करके संभव है यानी; एक सेट में वर्टेक्स को एक ही रंग से रंगा जाता है। यह एक C++ प्रोग्राम है जो 2 कलर एल्गोरिदम का उपयोग करके जांचता है कि कोई ग्राफ बाइपार्टाइट है या नहीं।
फंक्शन और स्यूडोकोड
Begin 1. isSafe() फंक्शन विकसित करें यह जांचने के लिए कि वर्तमान रंग असाइनमेंट वर्टेक्स v के लिए सुरक्षित है या नहीं, यानी जांचें कि एज मौजूद है या नहीं। यदि मौजूद है, तो अगला जांचें कि नए वर्टेक्स में भरा जाने वाला रंग पहले से ही इसके आसन्न वर्टेक्स द्वारा उपयोग किया गया है या नहीं। 2. function graphColoringtil(bool g[V][V], int k, int col[], int v) : g[V][V] = यह एक 2D ऐरे है जहां V ग्राफ में वर्टेक्स की संख्या है k = उपयोग किए जा सकने वाले रंगों की अधिकतम संख्या। col[] = एक कलर ऐरे जिसमें 1 से m तक की संख्याएं होनी चाहिए। if v == V return true For c = 1 to k if (isSafe(v, g, col, c)) col[v] = c if (graphColoringtil (g, k, col, v+1) == true) return true col[v] = 0 return false 3.function graphColoring(bool g[V][V], int k): for i = 0 to V-1 color[i] = 0 if (graphColoringtil(g, k, color, 0) == false) return false return true
उदाहरण
#include <iostream> #include <cstdio> #define V 4 using namespace std; bool isSafe (int v, bool g[V][V], int col[], int C) // m कलरिंग प्रॉब्लम को हल करने के लिए { for (int i = 0; i < V; i++) if (g[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)) // जांचें कि वर्टेक्स v को रंग c असाइन करना ठीक है { col[v] = c; if (graphColoringtil (g, k, col, v+1) == true) // शेष वर्टेक्स को रंग असाइन करने के लिए पुनरावृत्ति करें return true; col[v] = 0; // यदि रंग c असाइन करने से समाधान नहीं निकलता तो इसे हटा दें } } return false; }
आउटपुट
The graph is Bipartite
