Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम में DFS का उपयोग करके जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

समस्या विवरण

मान लीजिए हमारे पास एक जुड़ा हुआ ग्राफ है; हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। यदि दो रंगों को लागू करके ग्राफ रंगाई संभव है जैसे कि एक सेट में नोड्स को एक ही रंग से रंगा गया हो।

उदाहरण

यदि इनपुट ग्राफ (चित्र देखें) है, तो आउटपुट True होगा।

C++ प्रोग्राम में DFS का उपयोग करके जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

एल्गोरिदम चरण

  • फ़ंक्शन insert_edge(adj, u, v) परिभाषित करें जो आसन्न सूची में किनारे जोड़ता है।
  • मुख्य विधि से:
    • adj[v] में प्रत्येक u के लिए:
      • यदि visited[u] गलत है:
        • visited[u] := सत्य
        • color[u] := color[v] का उल्टा
        • यदि is_bipartite_graph(adj, u, visited, color) गलत है, तो गलत वापस करें
      • अन्यथा यदि color[u] == color[v], तो गलत वापस करें
    • सत्य वापस करें

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

void insert_edge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}

bool is_bipartite_graph(vector<int> adj[], int v, vector<bool>& visited, vector<int>& color){
    for (int u : adj[v]) {
        if (visited[u] == false) {
            visited[u] = true;
            color[u] = !color[v];
            if (!is_bipartite_graph(adj, u, visited, color))
                return false;
        }
        else if (color[u] == color[v])
            return false;
    }
    return true;
}

int main() {
    int N = 6;
    vector<int> adj_list[N + 1];
    vector<bool> visited(N + 1);
    vector<int> color(N + 1);
    insert_edge(adj_list, 1, 2);
    insert_edge(adj_list, 2, 3);
    insert_edge(adj_list, 3, 4);
    insert_edge(adj_list, 4, 5);
    insert_edge(adj_list, 5, 6);
    insert_edge(adj_list, 6, 1);
    visited[1] = true;
    color[1] = 0;
    cout << (is_bipartite_graph(adj_list, 1, visited, color));
}

इनपुट

insert_edge(adj_list, 1, 2); insert_edge(adj_list, 2, 3); insert_edge(adj_list, 3, 4); insert_edge(adj_list, 4, 5); insert_edge(adj_list, 5, 6); insert_edge(adj_list, 6, 1);

आउटपुट

1
  1. C++ प्रोग्राम: एडजेसेंसी मैट्रिक्स का उपयोग करके ग्राफ प्रतिनिधित्व करना C++ प्रोग्राम: एडजेसेंसी मैट्रिक्स का उपयोग करके ग्राफ प्रतिनिधित्व करना

    एक ग्राफ का एडजेसेंसी मैट्रिक्स V x V आकार का एक वर्ग मैट्रिक्स होता है। V ग्राफ G के वर्टेक्स की संख्या है। इस मैट्रिक्स में प्रत्येक तरफ V वर्टेक्स मार्क किए जाते हैं। यदि ग्राफ में i से j वर्टेक्स तक कुछ एज हैं, तो एडजेसेंसी मैट्रिक्स में i-वीं पंक्ति और j-वें कॉलम में 1 होगा (या वेटेड ग्राफ के

  1. C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना

    ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को पार करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जिसे विज़िट नहीं किया गया है, तो ग्राफ जुड़ा हुआ नहीं है। निर्देशित ग्राफ के लिए, हम कनेक्टिविटी जांचने के लिए सभी नोड्स से ट्रैवर्स

  1. पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

    मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो। उदाहरण के लिए, यदि