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

यूलर पथ एक ऐसा पथ है जिसके द्वारा हम प्रत्येक एज को ठीक एक बार विजिट कर सकते हैं। हम समान वर्टेक्स का उपयोग कई बार कर सकते हैं। एक ग्राफ जिसमें यूलर सर्किट होता है, इस मामले में भी माना जाता है, क्योंकि इसमें यूलर पथ भी होता है।

यह जांचने के लिए कि एक निर्देशित ग्राफ में यूलर पथ है या नहीं, हमें इन शर्तों की जांच करनी होगी:

• एक एकल वर्टेक्स aₙ होना चाहिए जहां (इन-डिग्री + 1 = आउट-डिग्री)
• एक एकल वर्टेक्स bₙ होना चाहिए जहां (इन-डिग्री = आउट-डिग्री + 1)
• बाकी सभी वर्टेक्स में (इन-डिग्री = आउट-डिग्री) होना चाहिए। यदि इनमें से कोई भी मामला विफल होता है, तो ग्राफ में कोई यूलर पथ नहीं है।

इनपुट

ग्राफ का आसन्नता मैट्रिक्स (Adjacency Matrix):

आउटपुट

यूलर पथ मिला।

एल्गोरिदम

traverse(u, visited)

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

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

isConnected(graph)

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

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

hasEulerPath(Graph)

इनपुट: दिया गया ग्राफ
आउटपुट: यूलर सर्किट मिलने पर True

Begin
    an := 0, bn := 0
    यदि isConnected() गलत है, तो false लौटाएं
    प्रत्येक नोड के लिए इनवर्ड और आउटवर्ड एज काउंट की सूची परिभाषित करें
    ग्राफ में सभी वर्टेक्स i के लिए:
        sum := 0
        i से जुड़े सभी वर्टेक्स j के लिए:
            वर्टेक्स i के लिए इनवर्ड एज बढ़ाएं
            sum बढ़ाएं
        किया
        वर्टेक्स i के आउटवर्ड एज की संख्या sum है
    किया
    
    यदि इनवर्ड सूची और आउटवर्ड सूची समान हैं, तो true लौटाएं (यूलर सर्किट)
    
    ग्राफ में सभी वर्टेक्स i के लिए:
        यदि inward[i] ≠ outward[i], तो:
            यदि inward[i] + 1 = outward[i], तो an++
            अन्यथा यदि inward[i] = outward[i] + 1, तो bn++
    किया
    
    यदि an और bn दोनों 1 हैं, तो true लौटाएं
    अन्यथा false लौटाएं
End

उदाहरण कोड

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

int graph[NODE][NODE] = {
    {0, 0, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 1},
    {1, 0, 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;
}

bool hasEulerPath() {
    int an = 0, bn = 0;
    if (!isConnected()) 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; // यूलर सर्किट
    
    for (int i = 0; i < NODE; i++) {
        if (inward[i] != outward[i]) {
            if (inward[i] + 1 == outward[i]) an++;
            else if (inward[i] == outward[i] + 1) bn++;
        }
    }
    
    return (an == 1 && bn == 1);
}

int main() {
    if (hasEulerPath())
        cout << "यूलर पथ मिला।";
    else
        cout << "कोई यूलर सर्किट नहीं।";
    return 0;
}

आउटपुट

यूलर पथ मिला।

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