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

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

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें insert_edge(), यह एक एज एरे लेगा adj, u, v,
adj[u] के अंत में v डालें
आपको adj[v] के अंत में सम्मिलित करें
मुख्य विधि से निम्न कार्य करें,
प्रत्येक आप के लिए adj[v],do
- यदि विज़िट किया गया[u] असत्य के समान है, तो −
  - विज़िट किया[यू] :=सच
  - रंग[यू] :=रंग का उलटा[v]
  - यदि is_bipartite_graph(adj, u, visit, color) नहीं है, तो −
    - झूठी वापसी
- अन्यथा जब रंग[u] रंग के समान हो[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);