একটি দ্বিভাজ্য গ্রাফ হল এমন গ্রাফ যেখানে গ্রাফ কলারিং (Graph Coloring) দুটি রঙ ব্যবহার করে সম্ভব। অর্থাৎ, একটি সেটের ভের্টেক্সগুলো একই রঙ দিয়ে রঙ করা যায়। এটি একটি সি++ প্রোগ্রাম যা DFS ব্যবহার করে গ্রাফটি দ্বিভাজ্য কিনা তা যাচাই করে।
অ্যালগরিদম
শুরু ১. একটি color[] অ্যারে ব্যবহার করা হয় যা প্রতিটি নোডের জন্য ০ বা ১ সংরক্ষণ করে যা বিপরীত রঙ নির্দেশ করে। ২. যেকোনো নোড থেকে DFS ফাংশন কল করুন। ৩. যদি নোড w আগে ভিজিট না করা থাকে, তবে !color[v] কে color[w]-এ অ্যাসাইন করুন এবং w-র সাথে সংযুক্ত নোডগুলো ভিজিট করতে আবার DFS কল করুন। ৪. যদি কোনো সময় color[u] সমান হয় !color[v]-এর সাথে, তবে নোডটি দ্বিভাজ্য। ৫. DFS ফাংশনটি সংশোধন করুন। শেষ
উদাহরণ
#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); //গ্রাফের ভের্টেক্সগুলো ২ রঙ দিয়ে রঙ করতে 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
