एक बाइपार्टाइट ग्राफ वह ग्राफ है जिसमें ग्राफ कलरिंग दो रंगों का उपयोग करके संभव है यानी; एक सेट में वर्टेक्स को एक ही रंग से रंगा जाता है। यह एक C++ प्रोग्राम है जो DFS का उपयोग करके जांचता है कि कोई ग्राफ बाइपार्टाइट है या नहीं।
एल्गोरिदम
Begin 1. एक कलर[] ऐरे का उपयोग किया जाता है जो प्रत्येक नोड के लिए 0 या 1 संग्रहीत करता है जो विपरीत रंगों को दर्शाता है। 2. किसी भी नोड से DFS फंक्शन को कॉल करें। 3. यदि नोड w पहले विज़िट नहीं किया गया है, तो !color[v] को color[w] असाइन करें और w से जुड़े नोड्स को विज़िट करने के लिए फिर से DFS कॉल करें। 4. यदि किसी भी स्थिति में, color[u], !color[v] के बराबर है, तो नोड बाइपार्टाइट है। 5. DFS फंक्शन को संशोधित करें End
उदाहरण
#include<iostream> #include <bits/stdc++.h> using namespace std; void addEd(vector<int> adj[], int w, int v) // ग्राफ में एज जोड़ना { adj[w].push_back(v); // w की सूची में v जोड़ें adj[v].push_back(w); // v की सूची में w जोड़ें } bool Bipartite(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color) { for (int w : adj[v]) { // यदि वर्टेक्स w पहले एक्सप्लोर नहीं किया गया है if (visited[w] == false) { // वर्तमान वर्टेक्स को विज़िटेड मार्क करें visited[w] = true; color[w] = !color[v]; // अपने पैरेंट के विपरीत रंग मार्क करें if (!Bipartite(adj, w, visited, color)) return false; } // यदि दो आसन्न वर्टेक्स एक ही रंग से रंगे हैं तो ग्राफ बाइपार्टाइट नहीं है else if (color[w] == color[v]) return false; } return true; } int main() { int M = 6; vector<int> adj[M + 1]; // इस बात पर नजर रखने के लिए // कि कोई नोड खोजा गया है या नहीं vector<bool> visited(M + 1); vector<int> color(M + 1); // ग्राफ के वर्टेक्स को 2 रंगों से रंगने के लिए addEd(adj, 3,2); addEd(adj, 1,4 ); addEd(adj, 2, 1); addEd(adj, 5,3); addEd(adj, 6,2); addEd(adj, 3,1); visited[1] = true; color[1] = 0; if (Bipartite(adj, 1, visited, color)) { cout << "Graph is Bipartite"; } else { cout << "Graph is not Bipartite"; } return 0; }
आउटपुट
Graph is not Bipartite
