Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


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

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

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

  • ग्राफ जुड़ा हुआ होना चाहिए।

  • प्रत्येक वर्टेक्स की इन-डिग्री और आउट-डिग्री समान होनी चाहिए।

इनपुट - ग्राफ का आसन्नता मैट्रिक्स।

01000
00100
00011
10000
00100

आउटपुट - यूलर सर्किट मिला

एल्गोरिदम

traverse(u, visited)

इनपुट - प्रारंभ नोड u और विज़िट किए गए नोड को चिह्नित करने के लिए कि कौन सा नोड विज़िट किया गया है।

आउटपुट - सभी जुड़े हुए वर्टेक्स को पार करें।

शुरुआत u को विज़िट के रूप में चिह्नित करें सभी वर्टेक्स v के लिए, यदि यह u के साथ आसन्न है, तो करें यदि v विज़िट नहीं किया गया है, तो traverse(v, visited) हो गया अंत

isConnected(graph)

इनपुट - ग्राफ।

आउटपुट - सच यदि ग्राफ जुड़ा हुआ है।

शुरुआत विज़िट किए गए सरणी को परिभाषित करें ग्राफ में सभी वर्टेक्स u के लिए, करें सभी नोड्स को अविज़िटेड बनाएं traverse(u, visited) यदि कोई अविज़िटेड नोड अभी भी शेष है, तो गलत वापस करें हो गया सच वापस करें अंत

isEulerCircuit(Graph)

इनपुट - दिया गया ग्राफ।

आउटपुट - सच जब एक यूलर सर्किट मिला।

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

उदाहरण कोड

#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;     //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; 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 << "यूलर सर्किट मिला."; else cout << "कोई यूलर सर्किट नहीं है."; }

आउटपुट

यूलर सर्किट मिला.

  1. C++ प्रोग्राम: BFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: BFS का उपयोग करके अनडायरेक्टेड ग्राफ की कनेक्टिविटी जांचना

    ग्राफ की कनेक्टिविटी जांचने के लिए, हम किसी भी ट्रैवर्सल एल्गोरिदम का उपयोग करके सभी नोड्स को ट्रैवर्स करने का प्रयास करेंगे। ट्रैवर्सल पूरा होने के बाद, यदि कोई नोड है, जो विजिट नहीं हुआ है, तो ग्राफ कनेक्टेड नहीं है। अनडायरेक्टेड ग्राफ के लिए, हम एक नोड चुनेंगे और उससे ट्रैवर्स करेंगे। इस मामले

  1. C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं C++ प्रोग्राम: जांचें कि क्या एक ग्राफ दृढ़ता से जुड़ा हुआ है या नहीं

    निर्देशित ग्राफ में घटकों को दृढ़ता से जुड़ा हुआ कहा जाता है, जब एक घटक में वर्टेक्स के प्रत्येक जोड़े के बीच एक पथ होता है। इस एल्गोरिदम को हल करने के लिए, पहले, प्रत्येक वर्टेक्स का फिनिश टाइम प्राप्त करने के लिए DFS एल्गोरिदम का उपयोग किया जाता है, अब ट्रांसपोज़्ड ग्राफ का फिनिश टाइम ढूंढें, फि

  1. C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना C++ प्रोग्राम: DFS का उपयोग करके निर्देशित ग्राफ की कनेक्टिविटी जांचना

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