C++ प्रोग्राम: जांचें कि अनिर्देशित ग्राफ में यूलरियन साइकिल है या नहीं

यूलर सर्किट के बारे में जानने के लिए, हमें यूलर पथ के बारे में पता होना चाहिए। यूलर पथ एक ऐसा पथ है जिसके द्वारा हम प्रत्येक नोड को ठीक एक बार विजिट कर सकते हैं। हम समान एज का उपयोग कई बार कर सकते हैं। यूलर सर्किट यूलर पथ का एक विशेष प्रकार है। जब यूलर पथ का प्रारंभिक वर्टेक्स उस पथ के अंतिम वर्टेक्स से भी जुड़ा होता है।

सर्किट का पता लगाने के लिए, हमें इन शर्तों का पालन करना होगा:

• ग्राफ कनेक्टेड होना चाहिए।
• अब जब एक अनिर्देशित ग्राफ के कोई वर्टेक्स की डिग्री विषम (odd) नहीं है, तो यह एक यूलर सर्किट है।

एल्गोरिदम

traverse(u, visited)

इनपुट: प्रारंभ नोड u और विजिटेड नोड सरणी
आउटपुट: सभी कनेक्टेड वर्टेक्स ट्रैवर्स करें

Begin
    u को विजिटेड मार्क करें
    सभी वर्टेक्स v के लिए, यदि u के साथ आसन्न है, तो:
        यदि v विजिटेड नहीं है, तो
            traverse(v, visited)
    किया
End

isConnected(graph)

इनपुट: ग्राफ
आउटपुट: ग्राफ कनेक्टेड है तो True

Begin
    विजिटेड सरणी परिभाषित करें
    ग्राफ में सभी वर्टेक्स u के लिए:
        सभी नोड्स को अनविजिटेड बनाएं
        traverse(u, visited)
        यदि कोई अनविजिटेड नोड शेष है, तो false लौटाएं
    किया
    true लौटाएं
End

hasEulerianCircuit(Graph)

इनपुट: दिया गया ग्राफ
आउटपुट: यूलरियन सर्किट न होने पर 0, होने पर 1

Begin
    यदि isConnected() गलत है, तो false लौटाएं
    प्रत्येक नोड के लिए डिग्री की सूची परिभाषित करें
    oddDegree := 0
    ग्राफ में सभी वर्टेक्स i के लिए:
        i से जुड़े सभी वर्टेक्स j के लिए:
            डिग्री बढ़ाएं
        किया
        यदि वर्टेक्स i की डिग्री विषम है, तो oddDegree बढ़ाएं
    किया
    यदि oddDegree 0 है, तो 1 लौटाएं
    अन्यथा 0 लौटाएं
End

उदाहरण कोड

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

// यूलर सर्किट वाला ग्राफ (सभी डिग्री सम)
int graph[NODE][NODE] = {
    {0, 1, 1, 1, 1},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {1, 0, 0, 1, 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 hasEulerianCircuit() {
    if (!isConnected()) return 0;
    
    vector<int> degree(NODE, 0);
    int oddDegree = 0;
    
    for (int i = 0; i < NODE; i++) {
        for (int j = 0; j < NODE; j++) {
            if (graph[i][j])
                degree[i]++;
        }
        if (degree[i] % 2 != 0)
            oddDegree++;
    }
    
    return (oddDegree == 0) ? 1 : 0;
}

int main() {
    if (hasEulerianCircuit())
        cout << "ग्राफ में यूलरियन सर्किट है।" << endl;
    else
        cout << "ग्राफ में कोई यूलरियन सर्किट नहीं है।" << endl;
    return 0;
}

आउटपुट

ग्राफ में यूलरियन सर्किट है।

यूलर पथ बनाम यूलर सर्किट (अनिर्देशित ग्राफ)

फ्लेरी का एल्गोरिदम और हायरहोल्जर का एल्गोरिदम वास्तविक पथ/सर्किट खोजने के लिए उपयोग किए जाते हैं (केवल अस्तित्व की जांच नहीं)।