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

C++ में फ्लेयूरी एल्गोरिदम से ऑयलरियन पाथ या सर्किट प्रिंट करें


फ्लेयूरी एल्गोरिदम का उपयोग दिए गए ग्राफ़ से ऑयलर पाथ या ऑयलर सर्किट प्रदर्शित करने के लिए किया जाता है। इस एल्गोरिदम में, एक एज से शुरू करके, यह पिछले वर्टेक्स को हटाकर अन्य एडजेसेंट वर्टेक्स की ओर जाने का प्रयास करता है। इस ट्रिक का उपयोग करके, ग्राफ़ प्रत्येक चरण में सरल होता जाता है ताकि ऑयलर पाथ या सर्किट मिल सके।

C++ में फ्लेयूरी एल्गोरिदम से ऑयलरियन पाथ या सर्किट प्रिंट करें

पाथ या सर्किट प्राप्त करने के लिए हमें कुछ नियमों की जांच करनी होगी -

  • ग्राफ़ एक ऑयलर ग्राफ़ होना चाहिए।
  • जब दो एज हों, एक ब्रिज हो और दूसरा नॉन-ब्रिज, तो हमें पहले नॉन-ब्रिज चुनना होगा।

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

इनपुट - ग्राफ़ का एडजेंसी मैट्रिक्स

01111
10111
11011
11101
11110

आउटपुट - ऑयलर पाथ या सर्किट: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2

एल्गोरिदम

findStartVert(graph) इनपुट: दिया गया ग्राफ़। आउटपुट: एल्गोरिदम शुरू करने के लिए स्टार्टिंग वर्टेक्स ढूंढें। Begin    ग्राफ़ में सभी वर्टेक्स i के लिए, करें       deg := 0       i के साथ एडजेसेंट सभी वर्टेक्स j के लिए, करें          deg := deg + 1       done       यदि deg ऑड है, तो          return i       done       जब सभी डिग्री इवन हों तो 0 रिटर्न करें End isBridge(u, v) इनपुट: स्टार्ट और एंड नोड। आउटपुट: जब u और v ब्रिज बना रहे हों तो True। Begin    deg := 0    v के साथ एडजेसेंट सभी वर्टेक्स i के लिए, करें       deg := deg + 1    done    if deg > 1, then       return false    return true End fleuryAlgorithm(start) इनपुट: स्टार्टिंग वर्टेक्स। आउटपुट: ऑयलर पाथ या सर्किट प्रदर्शित करें। Begin    edge := ग्राफ़ में एज की संख्या प्राप्त करें //यह अगले रिकर्सन कॉल में इनिशियलाइज़ नहीं होगा    start के साथ एडजेसेंट सभी वर्टेक्स v के लिए, करें       यदि edge <= 1 OR isBridge(start, v) false है, तो          start और v से पाथ प्रदर्शित करें          ग्राफ़ से एज (start,v) हटाएं          edge को 1 से घटाएं          fleuryAlgorithm(v)    done End

उदाहरण

#include<iostream> #include<vector> #define NODE 5 using namespace std; int graph[NODE][NODE] = {{0, 1, 1, 1, 1},    {1, 0, 1, 1, 0},    {1, 1, 0, 1, 0},    {1, 1, 1, 0, 1},    {1, 0, 0, 1, 0} }; int tempGraph[NODE][NODE]; int findStartVert(){    for(int i = 0; i<NODE; i++){       int deg = 0;       for(int j = 0; j<NODE; j++){          if(tempGraph[i][j])          deg++; //कनेक्टेड एज मिलने पर डिग्री बढ़ाएं       }       if(deg % 2 != 0) //जब वर्टेक्स की डिग्री ऑड हो       return i; //i ऑड डिग्री वाला नोड है    }    return 0; //जब सभी वर्टेक्स की डिग्री इवन हो, तो 0 से शुरू करें } bool isBridge(int u, int v){    int deg = 0;    for(int i = 0; i<NODE; i++)       if(tempGraph[v][i])          deg++;       if(deg>1){          return false; //एज ब्रिज नहीं बना रही       }    return true; //एज ब्रिज बना रही } int edgeCount(){    int count = 0;    for(int i = 0; i<NODE; i++)       for(int j = i; j<NODE; j++)          if(tempGraph[i][j])             count++;    return count; //ग्राफ़ में एज की संख्या गिनें } void fleuryAlgorithm(int start){    static int edge = edgeCount();    for(int v = 0; v<NODE; v++){       if(tempGraph[start][v]){ //जब (u,v) एज मौजूद है और ब्रिज नहीं बना रही          if(edge <= 1 || !isBridge(start, v)){             cout << start << "--" << v << " ";             tempGraph[start][v] = tempGraph[v][start] = 0; //ग्राफ़ से एज हटाएं             edge--; //एज घटाएं             fleuryAlgorithm(v);          }       }    } } int main(){    for(int i = 0; i<NODE; i++) //मेन ग्राफ़ को tempGraph में कॉपी करें    for(int j = 0; j<NODE; j++)    tempGraph[i][j] = graph[i][j];    cout << "Euler Path Or Circuit: ";    fleuryAlgorithm(findStartVert()); }

आउटपुट

Euler Path Or Circuit: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2

  1. C++ में अनसाइन्ड इंटीजर के लिए रीस्टोरिंग डिवीजन एल्गोरिथम C++ में अनसाइन्ड इंटीजर के लिए रीस्टोरिंग डिवीजन एल्गोरिथम

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

  1. मेमोरी मैनेजमेंट में बेस्ट फिट एल्गोरिदम के लिए C++ प्रोग्राम मेमोरी मैनेजमेंट में बेस्ट फिट एल्गोरिदम के लिए C++ प्रोग्राम

    दो ऐरे दिए गए हैं जिनमें ब्लॉक साइज़ और प्रोसेस साइज़ हैं; कार्य मेमोरी मैनेजमेंट में बेस्ट फिट एल्गोरिदम के अनुसार परिणाम प्रिंट करना है। बेस्ट फिट एल्गोरिदम क्या है? बेस्ट फिट एक मेमोरी मैनेजमेंट एल्गोरिदम है; यह सबसे छोटे फ्री पार्टीशन को आवंटित करने से संबंधित है जो अनुरोध करने वाले प्रोसेस की

  1. ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम के लिए C++ प्रोग्राम ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम के लिए C++ प्रोग्राम

    पेज नंबर और पेज साइज़ दिए गए हैं; कार्य ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम का उपयोग करके मेमोरी ब्लॉक को पेज में आवंटित करते समय हिट्स और मिस की संख्या ढूंढना है। ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम क्या है? ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम एक पेज रिप्लेसमेंट एल्गोरिदम है। एक पेज रिप्लेसमेंट एल्गोरि