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

C++ में स्रोत से k लंबाई से अधिक का पथ मौजूद है या नहीं खोजें


अवधारणा

एक दिए गए ग्राफ के संबंध में, ग्राफ में एक स्रोत शीर्ष और एक संख्या k (यहां k स्रोत शीर्ष और गंतव्य शीर्ष के बीच ग्राफ के पथ की लंबाई को इंगित करता है), हमारा कार्य यह निर्धारित करना है कि क्या दिया गया स्रोत से शुरू होकर किसी अन्य शीर्ष (यानी गंतव्य) पर समाप्त होने वाला एक सरल पथ (बिना किसी चक्र के) मौजूद है। ग्राफ निम्नलिखित में दिखाया गया है −

C++ में स्रोत से k लंबाई से अधिक का पथ मौजूद है या नहीं खोजें

इनपुट

Source s = 0, k = 64

आउटपुट

True

एक सरल पथ 0 -> 7 -> 1-> 2 -> 8 -> 6 -> 5 -> 3 -> 4 मौजूद है, जिसकी कुल दूरी 68 किमी है जो 64 से अधिक है।

इनपुट

Source s = 0, k = 70

आउटपुट

False

उपरोक्त ग्राफ में, सबसे लंबे सरल पथ की दूरी 69 है (0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8, इसलिए 69 से अधिक किसी भी इनपुट के लिए आउटपुट गलत होना चाहिए।

विधि

यह ध्यान दिया जाना चाहिए कि एक महत्वपूर्ण बात यह है कि केवल BFS (ब्रेडथ फर्स्ट सर्च) या DFS (डेप्थ फर्स्ट सर्च) करना और हर चरण पर सबसे लंबे किनारे का चयन करना काम नहीं करेगा। कारण यह है कि एक छोटा किनारा उच्च भार वाले किनारों से जुड़े होने के कारण लंबा पथ उत्पन्न कर सकता है।

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

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

उदाहरण

<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// Program to find if there is a simple path with // weight more than k #include<bits/stdc++.h> using namespace std; // iPair ==> Integer Pair typedef pair<int, int> iPair; // अब यह क्लास एक डायरेक्टेड ग्राफ को दर्शाता है // एडजेंसी सूची प्रतिनिधित्व का उपयोग करके class Graph{    int V1; // शीर्षों की संख्या इंगित करता है    // इस मामले में, एक वेटेड ग्राफ में, हमें शीर्ष    // और वजन जोड़ी को हर किनारे के लिए संग्रहीत करने की आवश्यकता है    list< pair<int, int>> *adj1;    bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1); public:    Graph(int V1); // कंस्ट्रक्टर दिखाता है    // ग्राफ में एक किनारा जोड़ने वाला फ़ंक्शन दिखाता है    void addEdge(int u1, int v1, int w1);    bool pathMoreThanK(int src1, int k); }; // सच लौटाता है यदि ग्राफ में k लंबाई से अधिक पथ है bool Graph::pathMoreThanK(int src1, int k){    // पथ सरणी बनाएं जिसमें कुछ भी शामिल न हो    // पथ में    vector<bool> path1(V1, false);    // स्रोत शीर्ष को पथ में जोड़ने के लिए उपयोग किया जाता है    path1[src1] = 1;    return pathMoreThanKUtil(src1, k, path1); } // src से अन्य सभी शीर्षों तक सबसे छोटे पथ प्रिंट करने के लिए उपयोग किया जाता है bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){    // अब यदि k 0 या ऋणात्मक है, तो सच लौटाएं;    if (k <= 0)       return true;    // स्रोत शीर्ष src के सभी आसन्न शीर्ष प्राप्त करने के लिए उपयोग किया जाता है और    // src से सभी पथों को पुनरावर्ती रूप से एक्सप्लोर करें।    list<iPair>::iterator i;    for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){       // आसन्न शीर्ष और किनारे का वजन प्राप्त करने के लिए उपयोग किया जाता है       int v1 = (*i).first;       int w1 = (*i).second;       // अब यदि शीर्ष v पहले से ही पथ में है, तो       // एक चक्र है (हम इस किनारे को अनदेखा करते हैं)       if (path1[v1] == true)          continue;       // अब यदि वजन k से अधिक है, तो सच लौटाएं       if (w1 >= k)          return true;       // अन्यथा इस शीर्ष को पथ में जोड़ें       path1[v1] = true;       // अब यदि यह आसन्न k से अधिक लंबा पथ प्रदान कर सकता है,       // तो सच लौटाएं।       if (pathMoreThanKUtil(v1, k-w1, path1))          return true;       // बैकट्रैक       path1[v1] = false;    }    // अब यदि कोई आसन्न लंबा पथ उत्पन्न नहीं कर सका, तो    // गलत लौटाएं       return false; } // एडजेंसी सूची के लिए मेमोरी आवंटित करने के लिए उपयोग किया जाता है Graph::Graph(int V1){    this->V1 = V1;    adj1 = new list<iPair> [V1]; } // एक किनारे (u, v) को वजन w के साथ जोड़ने के लिए उपयोगिता फ़ंक्शन दिखाता है void Graph::addEdge(int u1, int v1, int w1){    adj1[u1].push_back(make_pair(v1, w1));    adj1[v1].push_back(make_pair(u1, w1)); } // ग्राफ क्लास की विधियों का परीक्षण करने के लिए ड्राइवर प्रोग्राम int main(){    // उपरोक्त आकृति में दिए गए ग्राफ को बनाने के लिए उपयोग किया जाता है    int V1 = 9;    Graph g(V1);    // ऊपर दिखाए गए ग्राफ को बनाना    g.addEdge(0, 1, 5);    g.addEdge(0, 7, 9);    g.addEdge(1, 2, 9);    g.addEdge(1, 7, 12);    g.addEdge(2, 3, 8);    g.addEdge(2, 8, 3);    g.addEdge(2, 5, 10);    g.addEdge(3, 4, 10);    g.addEdge(3, 5, 15);    g.addEdge(4, 5, 11);    g.addEdge(5, 6, 3);    g.addEdge(6, 7, 2);    g.addEdge(6, 8, 7);    g.addEdge(7, 8, 8);    int src1 = 0;    int k = 70;    g.pathMoreThanK(src1, k)? cout << "Yes\n" :    cout << "No\n";    k = 68;    g.pathMoreThanK(src1, k)? cout << "Yes\n" :    cout << "No\n";    return 0; }

आउटपुट

No Yes

  1. C++ में दिए गए स्रोत से गंतव्य तक सभी पथ प्रिंट करें C++ में दिए गए स्रोत से गंतव्य तक सभी पथ प्रिंट करें

    इस समस्या में हमें एक निर्देशित ग्राफ दिया गया है और हमें ग्राफ के स्रोत से गंतव्य तक सभी पथ प्रिंट करने हैं। निर्देशित ग्राफ एक ग्राफ है जिसमें किनारे शीर्ष a से b की ओर निर्देशित होते हैं। समस्या को समझने के लिए एक उदाहरण लेते हैं स्रोत = K गंतव्य = P आउटपुट: P यहां, हमने K से P तक के पथ ढूंढे

  1. C++ में दिए गए प्रारंभिक वर्ण से सबसे लंबे लगातार पथ की लंबाई ज्ञात करें C++ में दिए गए प्रारंभिक वर्ण से सबसे लंबे लगातार पथ की लंबाई ज्ञात करें

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

  1. Python में स्रोत से k लंबाई से अधिक पथ है या नहीं ढूंढना Python में स्रोत से k लंबाई से अधिक पथ है या नहीं ढूंढना

    मान लीजिए हमारे पास एक ग्राफ है, हमारे पास एक स्रोत शीर्ष और एक संख्या k भी है। k स्रोत से गंतव्य तक ग्राफ का पथ लंबाई है, हमें जांचना है कि क्या हम स्रोत से शुरू होने वाला और किसी अन्य शीर्ष (गंतव्य के रूप में) पर समाप्त होने वाला एक सरल पथ (बिना चक्र के) ढूंढ सकते हैं। ग्राफ निम्नलिखित में दिखाया