ধরুন আমাদের একটি গাছ আছে, এবং সমস্ত নোডের ওজন এবং একটি পূর্ণসংখ্যা 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
ধারণা সহজ. আমরা গাছে ডিএফএস সম্পাদন করব, এবং নোডের ট্র্যাক রাখব, যার 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