ในปัญหานี้ เราได้รับต้นไม้ที่เชื่อมต่อแบบไม่มีทิศทาง T ที่มี n โหนด งานของเราคือการสร้างโปรแกรมเพื่อค้นหาผลคูณสูงสุดของเส้นทางที่ไม่ตัดกันสองเส้นในทรีใน 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
