C++で木構造における交差しない2つのパスの最大積を求める方法

本記事では、n個のノードからなる無向連結木Tが与えられたとき、互いに交差しない2つのパスの長さの積として考えられる最大値を求めるC++プログラムを作成します。

問題の説明

木構造の中から、共通の頂点や辺を一切共有しない「交差しないパス」を2つ選び出し、それぞれのパスの長さ(辺の数)を掛け合わせます。そして、その積が最大になるようなパスの組み合わせを見つけるのがこの問題の目的です。

具体例を使って問題を確認してみましょう。

入力

グラフ −

出力

8

解説

この例では、C-A-B と F-E-D-G-H の2つのパスが互いに交差していません。それぞれの長さは2と4であるため、積は 2 × 4 = 8 となり、これが求める最大値です。

解法のアプローチ

この問題はDFS(深さ優先探索)による木の走査を利用して解くことができます。基本的な考え方は次の通りです。

• 木から任意の1本の接続辺を取り除くと、木は2つの独立した部分木に分割されます。
• 各部分木について、DFSを用いてその内部の最長パス(直径)を求めます。
• すべての辺に対して「その辺を取り除いたときの2つの部分木の最長パスの積」を計算し、最大値を更新していきます。

DFSの実装では、各ノードから子方向へ伸ばせる最深距離の上位2つ(max1・max2)を追跡し、max1 + max2 をその部分木内の最長パス候補として答えを更新します。こうして得られた各候補の積のうち最大のものが、最終的な答えとなります。

なお、すべての辺についてDFSを実行するため、全体の計算量はO(n²)となります。

実装コード

上記の解法を実装したプログラムがこちらです。

#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

まとめ

木構造における交差しない2つのパスの最大積を求める問題は、「1本の辺を取り除いて木を2つの部分木に分割する」という発想と、DFSによる各部分木の最長パス(直径)計算を組み合わせることで効率よく解くことができます。木の直径を求めるテクニックは競技プログラミングなどでも応用範囲が広いため、ぜひマスターしておきましょう。