एक बाइपार्टाइट ग्राफ एक ग्राफ है जिसमें यदि ग्राफ कलरिंग केवल दो रंगों का उपयोग करके संभव है यानी; एक सेट में वर्टेक्स को उसी रंग से रंगा जाता है। यह C++ प्रोग्राम DFS का उपयोग करके जांचता है कि ग्राफ बाइपार्टाइट है या नहीं।
एल्गोरिदम
Begin एक ऐरे color[] का उपयोग प्रत्येक नोड के लिए 0 या 1 संग्रहीत करने के लिए किया जाता है जो विपरीत रंगों को दर्शाता है। किसी भी नोड से फंक्शन DFS कॉल करें। यदि नोड w पहले विज़िट नहीं किया गया है, तो !color[v] को color[w] असाइन करें और w से जुड़े नोड्स को विज़िट करने के लिए फिर से DFS कॉल करें। यदि किसी भी उदाहरण में, color[u], !color[v] के बराबर है, तो नोड बाइपार्टाइट है। 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
