ผลคูณสูงสุดของเส้นทางสองเส้นที่ไม่ตัดกันในต้นไม้ใน C++

ปัญหา

ในปัญหานี้ เราได้รับต้นไม้เชื่อมต่อไม่มีทิศทาง 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