एक बाइपार्टाइट ग्राफ वह ग्राफ है जिसमें ग्राफ कलरिंग दो रंगों का उपयोग करके संभव है यानी; एक सेट में वर्टेक्स को एक ही रंग से रंगा जाता है। यह एक C++ प्रोग्राम है जो BFS का उपयोग करके जांचता है कि कोई ग्राफ बाइपार्टाइट है या नहीं।
एल्गोरिदम
Begin Function Bipartite(): 1) सोर्स वर्टेक्स को एक रंग असाइन करें 2) पहले रंग को छोड़कर सभी पड़ोसियों को दूसरे रंग से रंगें। 3) पड़ोसी के पड़ोसियों को पहले रंग से रंगें। 4) इस तरह, सभी वर्टेक्स को रंग असाइन करें ताकि यह k वे कलरिंग प्रॉब्लम की सभी बाधाओं को पूरा करे जहां k = 2। 5) रंग असाइन करते समय, यदि हमें कोई पड़ोसी मिलता है जो वर्तमान वर्टेक्स के समान रंग से रंगा हुआ है, तो ग्राफ को 2 वर्टेक्स से रंगा नहीं जा सकता यानी; ग्राफ बाइपार्टाइट नहीं है End
उदाहरण
#include <iostream> #include <queue> #define V 5 using namespace std; bool Bipartite(int G[][V], int s) { int colorA[V]; for (int i = 0; i < V; ++i) colorA[i] = -1; colorA[s] = 1; // सोर्स वर्टेक्स को एक रंग असाइन करें queue <int> q; // वर्टेक्स नंबर की एक क्यू बनाएं और BFS ट्रैवर्सल के लिए सोर्स वर्टेक्स को एनक्यू करें q.push(s); while (!q.empty()) { int w = q.front(); // एक वर्टेक्स डी-क्यू करें q.pop(); for (int v = 0; v < V; ++v) // सभी नॉन-कलर्ड आसन्न वर्टेक्स ढूंढें { if (G[w][v] && colorA[v] == -1) // w से v तक एक एज मौजूद है और डेस्टिनेशन v कलर्ड नहीं है { colorA[v] = 1 - colorA[w]; // w के इस आसन्न v को वैकल्पिक रंग असाइन करें q.push(v); } else if (G[w][v] && colorA[v] == colorA[w]) // w से v तक एक एज मौजूद है और डेस्टिनेशन // v उसी रंग से रंगा है जैसे u return false; } } return true; // यदि सभी आसन्न वर्टेक्स को वैकल्पिक रंग से रंगा जा सकता है } int main() { int G[][V] = {{ 0, 1, 0, 0}, { 1, 0, 0, 0}, { 0, 0, 0, 1}, { 1, 0, 1, 0}}; if (Bipartite(G, 0)) cout << "The Graph is Bipartite"<<endl; else cout << "The Graph is Not Bipartite"<<endl; return 0; }
आउटपुट
The Graph is Bipartite
