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

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

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

• ग्राफ कनेक्टेड होना चाहिए।
• अब जब एक अनिर्देशित ग्राफ के कोई वर्टेक्स की डिग्री विषम (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

isEulerian(Graph)

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

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

उदाहरण कोड

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

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {0, 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 isEulerian() {
    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++;
    }
    
    if (oddDegree > 2) return 0;
    return 1; // 0 = यूलर सर्किट, 2 = यूलर पथ
}

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

आउटपुट

ग्राफ में यूलरियन पथ है।

मुख्य शर्तें सारांश (अनिर्देशित ग्राफ)

नोट: विषम डिग्री वाले वर्टेक्स की संख्या हमेशा सम होती है (हैंडशेकिंग लेम्मा)।