C++-এ নির্দেশিত গ্রাফ সংযুক্ত কিনা তা যাচাই করা

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

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

এই ক্ষেত্রে ট্রাভার্সাল অ্যালগরিদম হল রিকারসিভ DFS ট্রাভার্সাল।

ইনপুট

একটি গ্রাফের এডজেসেন্সি ম্যাট্রিক্স

আউটপুট

গ্রাফটি সংযুক্ত।

অ্যালগরিদম

traverse(u, visited) 
ইনপুট: স্টার্ট নোড u এবং ভিজিটেড নোড অ্যারে যা কোন নোড ভিজিটেড সেটা মার্ক করে। 
আউটপুট: সমস্ত সংযুক্ত ভের্টেক্স ট্রাভার্স করা। 
শুরু 
    u কে ভিজিটেড হিসেবে মার্ক করো
    u-এর সাথে এডজেসেন্ট সকল ভের্টেক্স v জন্য, করো
        যদি v ভিজিটেড না হয়, তবে
            traverse(v, visited)
        শেষ যদি
    শেষ ফর
শেষ

isConnected(graph) 
ইনপুট: গ্রাফ। 
আউটপুট: গ্রাফ সংযুক্ত হলে True। 
শুরু 
    visited অ্যারে ডিফাইন করো
    গ্রাফের সকল ভের্টেক্স u জন্য, করো
        সকল নোডকে অনভিজিটেড বানাও
        traverse(u, visited)
        যদি কোনো অনভিজিটেড নোড অবশিষ্ট থাকে, তবে
            false রিটার্ন করো
        শেষ যদি
    শেষ ফর
    true রিটার্ন করো
শেষ

উদাহরণ (C++ কোড)

#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; // v কে ভিজিটেড হিসেবে মার্ক করো
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    // সব ভের্টেক্স u কে স্টার্ট পয়েন্ট হিসেবে ধরে চেক করো যে সকল নোড ভিজিবল কিনা
    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.