গ্রাফে কানেক্টেড কম্পোনেন্ট খোঁজা#

$n$ টি নোড এবং $m$ টি এজ বিশিষ্ট একটি আনডিরেক্টেড গ্রাফ $G$ দেওয়া আছে। আমাদের এতে সব কানেক্টেড কম্পোনেন্ট খুঁজে বের করতে হবে, অর্থাৎ ভার্টেক্সের এমন কয়েকটি গ্রুপ যেখানে একটি গ্রুপের ভেতরে প্রতিটি ভার্টেক্স থেকে অন্য যেকোনো ভার্টেক্সে পৌঁছানো যায় এবং ভিন্ন গ্রুপের মধ্যে কোনো পাথ নেই।

সমস্যা সমাধানের অ্যালগরিদম#

  • সমস্যা সমাধানের জন্য, আমরা ডেপথ ফার্স্ট সার্চ বা ব্রেডথ ফার্স্ট সার্চ ব্যবহার করতে পারি।

  • আসলে, আমরা DFS-এর কয়েকটি রাউন্ড চালাব: প্রথম রাউন্ড প্রথম নোড থেকে শুরু হবে এবং প্রথম কানেক্টেড কম্পোনেন্টের সব নোড ট্রাভার্স (খুঁজে পাওয়া) হবে। তারপর বাকি নোডগুলোর মধ্যে প্রথম অভিজিত নোড খুঁজে সেটি থেকে ডেপথ ফার্স্ট সার্চ চালাব, এভাবে দ্বিতীয় কানেক্টেড কম্পোনেন্ট পাওয়া যাবে। এভাবে চলতে থাকবে যতক্ষণ না সব নোড ভিজিট করা হয়।

  • এই অ্যালগরিদমের মোট অ্যাসিম্পটটিক রানিং টাইম $O(n + m)$: আসলে, এই অ্যালগরিদম একই ভার্টেক্সে দুইবার চলবে না, যার মানে প্রতিটি এজ ঠিক দুইবার দেখা হবে (একপ্রান্তে এবং অন্যপ্রান্তে)।

ইমপ্লিমেন্টেশন#

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;

void dfs(int v) {
    used[v] = true;
    comp.push_back(v);
    for (int u : adj[v]) {
        if (!used[u])
            dfs(u);
    }
}

void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

  • সবচেয়ে গুরুত্বপূর্ণ ফাংশন হলো find_comps() যেটি গ্রাফের কানেক্টেড কম্পোনেন্টগুলো খুঁজে বের করে এবং প্রদর্শন করে।

  • গ্রাফটি অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশনে সংরক্ষিত, অর্থাৎ adj[v] ভার্টেক্স v থেকে এজযুক্ত ভার্টেক্সগুলোর তালিকা ধারণ করে।

  • comp ভেক্টরটি বর্তমান কানেক্টেড কম্পোনেন্টের নোডগুলোর তালিকা ধারণ করে।

কোডের ইটারেটিভ ইমপ্লিমেন্টেশন#

গভীর রিকার্সিভ ফাংশন সাধারণত সমস্যাজনক। প্রতিটি রিকার্সিভ কলে স্ট্যাকে সামান্য মেমোরি প্রয়োজন হয়, এবং ডিফল্টভাবে প্রোগ্রামগুলোর সীমিত স্ট্যাক স্পেস থাকে। তাই যখন আপনি লক্ষ লক্ষ নোড বিশিষ্ট কানেক্টেড গ্রাফে রিকার্সিভ DFS চালান, আপনি স্ট্যাক ওভারফ্লোতে পড়তে পারেন।

রিকার্সিভ প্রোগ্রামকে সর্বদা ইটারেটিভ প্রোগ্রামে রূপান্তর করা সম্ভব, ম্যানুয়ালি একটি স্ট্যাক ডেটা স্ট্রাকচার বজায় রেখে। যেহেতু এই ডেটা স্ট্রাকচার হিপে অ্যালোকেট হয়, কোনো স্ট্যাক ওভারফ্লো হবে না।

int n;
vector<vector<int>> adj;
vector<bool> used;
vector<int> comp;

void dfs(int v) {
    stack<int> st;
    st.push(v);

    while (!st.empty()) {
        int curr = st.top();
        st.pop();
        if (!used[curr]) {
            used[curr] = true;
            comp.push_back(curr);
            for (int i = adj[curr].size() - 1; i >= 0; i--) {
                st.push(adj[curr][i]);
            }
        }
    }
}

void find_comps() {
    used.assign(n, false);
    for (int v = 0; v < n ; ++v) {
        if (!used[v]) {
            comp.clear();
            dfs(v);
            cout << "Component:" ;
            for (int u : comp)
                cout << ' ' << u;
            cout << endl ;
        }
    }
}

অনুশীলন সমস্যা#