C++ প্রোগ্রাম: নির্দেশিত গ্রাফে অয়লার চক্র আছে কিনা যাচাই

অয়লার চক্র/সার্কিট হল একটি পথ; যার মাধ্যমে আমরা প্রতিটি এজ ঠিক একবার ভিজিট করতে পারি। আমরা একই ভার্টেক্স একাধিকবার ব্যবহার করতে পারি। অয়লার সার্কিট হল অয়লার পথের একটি বিশেষ ধরন। যখন অয়লার পথের শুরুর ভার্টেক্স সেই পথের শেষ ভার্টেক্সের সাথে সংযুক্ত থাকে, তখন সেটিকে অয়লার সার্কিট বলা হয়।

একটি গ্রাফ অয়লারিয়ান কিনা তা চেক করতে দুটি শর্ত পূরণ করতে হয়:

• গ্রাফটি অবশ্যই কানেক্টেড হতে হবে।

• প্রতিটি ভার্টেক্সের ইন-ডিগ্রি এবং আউট-ডিগ্রি একই হতে হবে।

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

আউটপুট − Euler Circuit Found

অ্যালগরিদম

traverse(u, visited)

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

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

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

isConnected(graph)

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

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

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

isEulerCircuit(Graph)

ইনপুট − দত্তক গ্রাফ।

আউটপুট − একটি অয়লার সার্কিট পাওয়া গেলে true।

শুরু
    যদি isConnected() false হয়, তবে
        false ফেরত দাও
    ইনওয়ার্ড এবং আউটওয়ার্ড এজ কাউন্টের জন্য লিস্ট ডিফাইন করুন
    গ্রাফের সব ভার্টেক্স i-এর জন্য
        sum := 0
        i-র সাথে সংযুক্ত সব ভার্টেক্স j-এর জন্য
            ভার্টেক্স i-এর ইনওয়ার্ড এজ বাড়ান
            sum বাড়ান
        শেষ
        ভার্টেক্স i-এর আউটওয়ার্ড সংখ্যা = sum
    শেষ
    যদি ইনওয়ার্ড লিস্ট এবং আউটওয়ার্ড লিস্ট একই হয়, তবে
        true ফেরত দাও
    অন্যথায় false ফেরত দাও
শেষ

উদাহরণ কোড

#include <iostream>
#include <vector>
#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, 0, 1, 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;
}

bool isEulerCircuit() {
    if(isConnected() == false) {
        return false;
    }
    vector<int> inward(NODE, 0), outward(NODE, 0);
    for(int i = 0; i < NODE; i++) {
        int sum = 0;
        for(int j = 0; j < NODE; j++) {
            if(graph[i][j]) {
                inward[j]++;
                sum++;
            }
        }
        outward[i] = sum;
    }
    if(inward == outward)
        return true;
    return false;
}

int main() {
    if(isEulerCircuit())
        cout << "Euler Circuit Found.";
    else
        cout << "There is no Euler Circuit.";
}

আউটপুট

Euler Circuit Found.