मान लीजिए हमारे पास एक ट्री है, और सभी नोड्स के वजन और एक पूर्णांक x है। हमें नोड i ढूंढना है, जैसे कि |weight[i] - x| न्यूनतम हो। यदि ग्राफ नीचे की तरह है, और x = 15
आउटपुट 3 होगा। अब विभिन्न नोड्स के लिए, यह नीचे की तरह होगा:
नोड 1, |5 – 15| = 10
नोड 2, |10 – 15| = 5
नोड 3, |11 – 15| = 4
नोड 4, |8 – 15| = 7
नोड 5, |6 – 15| = 9
विचार सरल है। हम ट्री पर DFS करेंगे, और उस नोड को ट्रैक करेंगे, जिसका भारित निरपेक्ष अंतर x के साथ न्यूनतम मान देता है।
उदाहरण
#include <iostream> #include <vector> #include <cmath> using namespace std; int min_value = INT_MAX, x, result; vector<int> graph[100]; vector<int> weight(100); void dfs(int node, int parent) { if (min_value > abs(weight[node] - x)) { min_value = abs(weight[node] - x); result = node; } for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); } } int main() { x = 15; weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; graph[1].push_back(2); graph[2].push_back(3); graph[2].push_back(4); graph[1].push_back(5); dfs(1, 1); cout << "The node number is: " << result; } आउटपुट
The node number is: 3
