C++ প্রোগ্রাম: DFS ব্যবহার করে নির্দেশিত গ্রাফের কানেক্টিভিটি যাচাই

একটি গ্রাফের কানেক্টিভিটি চেক করতে, আমরা যেকোনো ট্রভারসাল অ্যালগরিদম ব্যবহার করে সব নোড ট্রভার্স করার চেষ্টা করব। ট্রভারসাল সম্পূর্ণ হলে, যদি কোনো নোড অনভিজিটেড থাকে, তবে গ্রাফটি কানেক্টেড নয়।

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

এখানে ট্রভারসাল অ্যালগরিদম হল রিকার্সিভ DFS ট্রভারসাল।

ইনপুট: একটি গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স

আউটপুট: The Graph is connected.

অ্যালগরিদম

traverse(u, visited)

ইনপুট: শুরুর নোড u এবং ভিজিটেড নোড যা কোন নোড ভিজিটেড সেটা মার্ক করে।

আউটপুট: সব সংযুক্ত ভার্টেক্স ট্রভার্স করুন।

শুরু
    u কে ভিজিটেড মার্ক করুন
    সব ভার্টেক্স v-এর জন্য, যদি u-এর সাথে অ্যাডজেসেন্ট থাকে, তবে
        যদি v ভিজিটেড না থাকে, তবে traverse(v, visited)
    শেষ
শেষ

isConnected(graph)

ইনপুট: গ্রাফ।

আউটপুট: গ্রাফ কানেক্টেড হলে true।

শুরু
    ভিজিটেড অ্যারে ডিফাইন করুন
    গ্রাফের সব ভার্টেক্স u-এর জন্য
        সব নোড আনভিজিটেড করুন
        traverse(u, visited)
        যদি কোনো আনভিজিটেড নোড বাকি থাকে, তবে false ফেরত দাও
    শেষ
    true ফেরত দাও
শেষ

উদাহরণ কোড

#include <iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {{0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0}};

void traverse(int u, bool visited[]) {
    visited[u] = true;
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false;
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i])
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected())
        cout << "The Graph is connected.";
    else
        cout << "The Graph is not connected.";
}

আউটপুট

The Graph is connected.