কম্পিউটার

DFS ব্যবহার করে গ্রাফ একটি দ্বিপক্ষীয় কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম


একটি দ্বিপক্ষীয় গ্রাফ হল একটি গ্রাফ যেখানে যদি দুটি রঙ ব্যবহার করে গ্রাফ রঙ করা সম্ভব হয় যেমন; একটি সেটের শীর্ষবিন্দু একই রঙে রঙিন হয়। এটি একটি C++ প্রোগ্রাম যা একটি গ্রাফ দ্বিপক্ষীয় কিনা ডিএফএস ব্যবহার করছে কিনা তা পরীক্ষা করার জন্য।

অ্যালগরিদম

Begin
   1. An array color[] is used to stores 0 or 1 for every node which denotes opposite colors.
   2. Call function DFS from any node.
   3. If the node w has not been visited previously, then assign !
      color[v] to color[w] and call DFS again to visit nodes connected to w.
   4. If at any instance, color[u] is equal to !color[v], then the node is bipartite.
   5. Modify the DFS function
End

উদাহরণ

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
void addEd(vector<int> adj[], int w, int v) //adding edge to the graph {
   adj[w].push_back(v); //add v to w’s list
   adj[v].push_back(w); //add w to v’s list
}
bool Bipartite(vector<int> adj[], int v,
vector<bool>& visited, vector<int>& color) {
   for (int w : adj[v]) {
      // if vertex w is not explored before
      if (visited[w] == false) {
         // mark present vertex as visited
         visited[w] = true;
         color[w] = !color[v]; //mark color opposite to its parents
         if (!Bipartite(adj, w, visited, color))
            return false;
      }
      // if two adjacent are colored with same color then the graph is not bipartite
         else if (color[w] == color[v])
            return false;
   }
   return true;
}
int main() {
   int M = 6;
   vector<int> adj[M + 1];
   // to keep a check on whether
   // a node is discovered or not
   vector<bool> visited(M + 1);
   vector<int> color(M + 1); //to color the vertices of the graph with 2 color
   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

  1. একটি অনির্দেশিত গ্রাফে ইউলারিয়ান চক্র রয়েছে কিনা তা পরীক্ষা করার জন্য C++ প্রোগ্রাম

  2. ডিএফএস ব্যবহার করে অনির্দেশিত গ্রাফের সংযোগ পরীক্ষা করার জন্য C++ প্রোগ্রাম

  3. একটি গ্রাফ দৃঢ়ভাবে সংযুক্ত কি না তা পরীক্ষা করার জন্য C++ প্রোগ্রাম

  4. ডিএফএস ব্যবহার করে নির্দেশিত গ্রাফের সংযোগ পরীক্ষা করার জন্য C++ প্রোগ্রাম