सी ++ में एक पेड़ में दो गैर-अंतर्विभाजक पथों का अधिकतम उत्पाद

इस समस्या में, हमें n नोड्स के साथ एक अप्रत्यक्ष कनेक्टेड ट्री T दिया जाता है। हमारा कार्य C++ में एक ट्री में दो गैर-अंतर्विभाजकपथों के अधिकतम उत्पाद को खोजने के लिए एक प्रोग्राम बनाना है।

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

ग्राफ़ -

आउटपुट

8

स्पष्टीकरण

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

लंबाई 2 और 4 हैं। उत्पाद =8.

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

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

हमारे समाधान को लागू करने के लिए कार्यक्रम,

उदाहरण

#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