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

C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल


इस समस्या में, हमें n नोड्स के साथ एक अविभाजित कनेक्टेड ट्री T दिया गया है। हमारा कार्य C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए एक प्रोग्राम बनाना है।

समस्या विवरण - ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल ढूंढने के लिए। हम सभी गैर-प्रतिच्छेदी पथ ढूंढेंगे और फिर उनकी लंबाई का गुणनफल ढूंढेंगे।

आइए एक उदाहरण से समस्या को समझते हैं,

इनपुट

ग्राफ -

C++ में ट्री में दो गैर-प्रतिच्छेदी पथों का अधिकतम गुणनफल

आउटपुट

8

व्याख्या

विचार किए गए गैर-प्रतिच्छेदी पथ हैं C-A-B और F-E-D-G-H।

लंबाई 2 और 4 हैं। गुणनफल = 8।

समाधान दृष्टिकोण

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

हमारे समाधान को लागू करने वाला प्रोग्राम,

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
int TreeTraverse(vector<int> graph[], int& currPathMax, int val1, int val2){ 
    int max1 = 0, max2 = 0, maxVal = 0; 
    for (int i = 0; i < graph[val1].size(); i++) { 
        if (graph[val1][i] == val2) 
            continue; 
        maxVal = max(maxVal, TreeTraverse(graph, currPathMax, 
            graph[val1][i], val1)); 
        if (currPathMax > max1) { 
            max2 = max1; 
            max1 = currPathMax; 
        } 
        else 
            max2 = max(max2, currPathMax); 
    } 
    maxVal = max(maxVal, max1 + max2); 
    currPathMax = max1 + 1; 
    return maxVal; 
} 
int FindMaxProductPath(vector<int> graph[], int Size) { 
    int maxProd = -10; 
    int pathA, pathB; 
    int currPathMax, prod; 
    for (int i = 0; i < Size; i++) { 
        for (int j = 0; j < graph[i].size(); j++){ 
            currPathMax = 0; 
            pathA = TreeTraverse(graph, currPathMax, graph[i][j],i); 
            currPathMax = 0; 
            pathB = TreeTraverse(graph, currPathMax, i,graph[i][j]); 
            prod = (pathA * pathB); 
            maxProd = max(maxProd, prod); 
        } 
    } 
    return maxProd; 
} 
void insertEdge(vector<int> graph[], int val1, int val2){ 
    graph[val1].push_back(val2); 
    graph[val2].push_back(val1); 
} 
int main(){ 
    int Size = 8; 
    vector<int> graph[Size + 2]; 
    insertEdge(graph, 1, 2); 
    insertEdge(graph, 2, 4); 
    insertEdge(graph, 3, 1); 
    insertEdge(graph, 5, 4); 
    insertEdge(graph, 7, 8); 
    insertEdge(graph, 8, 4); 
    insertEdge(graph, 5, 6); 
    cout<<"Maximum product of two non-intersecting paths of tree is "<<FindMaxProductPath(graph, Size)<<"\n"; 
    return 0; 
}

आउटपुट

Maximum product of two non-intersecting paths of tree is 8
  1. C++ में ट्री डायमीटर C++ में ट्री डायमीटर

    मान लीजिए हमारे पास एक अनडायरेक्टेड ट्री है; हमें इसका डायमीटर ढूंढना है - उस ट्री में सबसे लंबे पथ में एज की संख्या उस ट्री का डायमीटर है। यहां ट्री को एज लिस्ट के रूप में दिया गया है जहां edges[i] = [u, v] नोड्स u और v के बीच एक बायडायरेक्शनल एज है। प्रत्येक नोड के लेबल सेट {0, 1, ..., edges.lengt

  1. C++ में बाइनरी ट्री में अधिकतम लेवल उत्पाद ढूंढें C++ में बाइनरी ट्री में अधिकतम लेवल उत्पाद ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें पॉजिटिव और नेगेटिव नोड्स हैं। हमें इसके प्रत्येक लेवल पर अधिकतम उत्पाद ढूंढना है। इसे ट्री मानें, तो लेवल 0 का उत्पाद 4 है, लेवल 1 का उत्पाद 2 * -5 = -10 है, और लेवल 2 का उत्पाद -1 * 3 * -2 * 6 = 36 है। तो यह अधिकतम है। इसे हल करने के लिए, हम ट्री का

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज