C++でXとの絶対差が最小となるノードを見つける方法

問題の概要

木構造と各ノードの重み、そして整数 x が与えられたとき、|weight[i] − x| の値が最小となるノード i を見つける問題を考えてみましょう。例えば、下図のような木があり、x = 15 とします。

この場合、出力は 3 となります。各ノードについて絶対差を計算すると、以下のようになります。

• ノード 1:|5 − 15| = 10
• ノード 2:|10 − 15| = 5
• ノード 3:|11 − 15| = 4
• ノード 4:|8 − 15| = 7
• ノード 5:|6 − 15| = 9

絶対差が最小となるのはノード 3 の「4」であるため、答えは 3 です。

アルゴリズムの考え方

アプローチは非常にシンプルです。木に対してDFS(深さ優先探索)を実行し、各ノードを訪問するたびに「そのノードの重みと x の絶対差」を現在の最小値と比較します。より小さい値が見つかれば、最小値と該当ノードの番号を更新していきます。すべてのノードを訪問し終えた時点で記録されているノードが答えとなります。

計算量

DFSですべてのノードを一度ずつ訪問するため、時間計算量は O(N)(N はノード数)です。ノード数が多い木でも効率的に処理できます。

C++による実装例

#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

コードの解説

• dfs 関数:現在のノードの重みと x の絶対差が min_value より小さい場合、min_value と result を更新します。
• parent 引数:隣接ノードが親ノードと同じ場合は探索をスキップすることで、木を逆方向にたどる無限ループを防ぎます。
• main 関数:各ノードの重みと辺の情報を設定し、ルート(ノード 1)から DFS を開始します。

このように、DFSを用いることで木構造上の任意の条件を満たすノードを簡単に探索できます。比較条件を変更すれば、「最大の絶対差を持つノード」や「特定の範囲内の重みを持つノード」など、さまざまな応用問題にも対応可能です。