หาโหนดที่ค่าสัมบูรณ์ของ (Weight - X) น้อยที่สุดใน Tree (C++)

ให้ Tree ที่มีน้ำหนัก (Weight) ที่แต่ละโหนด และค่า X หาโหนดที่ทำให้ |Weight[i] - X| น้อยที่สุด

X = 15, โหนดที่ 3 (Weight = 11) ให้ |11-15| = 4 น้อยที่สุด

อัลกอริทึม

ใช้ DFS (Depth First Search) เดินทั่ว Tree เก็บค่าความต่างสัมบูรณ์ที่น้อยที่สุด และโหนดที่สอดคล้อง

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int min_value = INT_MAX;
int x, result;
vector graph[100];
vector weight(100);

void dfs(int node, int parent) {
    int diff = abs(weight[node] - x);
    if (diff < min_value) {
        min_value = diff;
        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;

    return 0;
}

ผลลัพธ์

The node number is: 3

การคำนวณยืนยัน

• Node 1: |5-15| = 10
• Node 2: |10-15| = 5
• Node 3: |11-15| = 4 ← น้อยที่สุด
• Node 4: |8-15| = 7
• Node 5: |6-15| = 9

ความซับซ้อน

เวลา: O(V + E), พื้นที่: O(V) สำหรับ Recursion Stack