C++ প্রোগ্রাম: DFS ব্যবহার করে বাইপার্টাইট গ্রাফ যাচাই

বাইপার্টাইট গ্রাফ কী?

একটি গ্রাফ বাইপার্টাইট হলে তার ভেরটেক্সগুলিকে দুটি সেটে ভাগ করা যায় যাতে প্রতিটি এজ এক সেট থেকে অন্য সেটে যায়। সমানভাবে, গ্রাফটি ২-রঙে রঙ করা যায় যাতে কোনো এজের দুটি এন্ডপয়েন্ট একই রঙের না হয়।

এলগরিদম (DFS-ভিত্তিক)

1. সব নোডের জন্য `color` অ্যারে ইনিশিয়ালাইজ করুন (-1 = আনভিজিটেড, 0/1 = দুটি রঙ)।
2. কোনো আনভিজিটেড নোড থেকে DFS শুরু করুন, রঙ ০ দিয়ে।
3. প্রতিটি নেইবার `v` এর জন্য:
   • যদি আনভিজিটেড হয় → বিপরীত রঙ দিয়ে রিকার্শিভলি DFS কল করুন।
   • যদি ইতিমধ্যে ভিজিটেড হয় এবং একই রঙ পাওয়া যায় → বাইপার্টাইট নয়।
4. সব কম্পোনেন্ট কভার না হলে অন্য আনভিজিটেড নোড থেকে রিপিট করুন।

উদাহরণ কোড

#include <iostream>
#include <vector>
using namespace std;

bool dfsBipartite(int u, vector<vector<int>>& adj, vector<int>& color) {
    for (int v : adj[u]) {
        if (color[v] == -1) {
            color[v] = 1 - color[u]; // Opposite color
            if (!dfsBipartite(v, adj, color))
                return false;
        } else if (color[v] == color[u]) {
            return false; // Same color on adjacent nodes
        }
    }
    return true;
}

bool isBipartite(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            color[i] = 0;
            if (!dfsBipartite(i, adj, color))
                return false;
        }
    }
    return true;
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };

    // Example edges
    addEdge(2, 1); // 3-2 (0-indexed: 2,1)
    addEdge(0, 3); // 1-4
    addEdge(1, 0); // 2-1
    addEdge(4, 2); // 5-3
    addEdge(5, 1); // 6-2
    addEdge(2, 0); // 3-1

    cout << (isBipartite(adj) ? "Graph is Bipartite" : "Graph is not Bipartite") << "\n";
    return 0;
}

আউটপুট

Graph is not Bipartite

ব্যাখ্যা

দেওয়া গ্রাফে অড্ড-লেন্থ সাইকেল (১-২-৩-১) রয়েছে, তাই এটি বাইপার্টাইট নয়। DFS-ভিত্তিক ২-রঙ পদ্ধতিতে O(V+E) টাইমে বাইপার্টাইটネス চেক করা যায়। BFS-ও ব্যবহার করা যায়।