C++でDFSを使ってn分木のすべての葉ノードを出力する方法

問題の概要

この問題では、n分木（n-ary tree）の辺情報を格納した2次元配列が与えられます。配列の各要素は木の辺を表しており、この配列から構成されるn分木のすべての葉ノード（リーフノード）を出力することが求められます。

n分木とは、各ノードが最大でn個の子を持つことができる木構造のことです。つまり、あるノードは1個、2個……n個までの子ノードを持つ可能性があります。

入出力例

Input: edge[][] = {{5,8}, {5,6}, {8,1}, {8,4}, {6,7}}
Output: 1 4 7

解説 − 辺配列をもとに木を構築すると、次のような構造になります。

この木の葉ノードは 1、4、7 です。

解決アプローチ

この問題を解くには、DFS（深さ優先探索）を用いて木を走査します。走査の過程で各部分木の葉ノードを順次見つけ出し、訪問済みノードは配列でマークして管理します。あるノードに子ノードが存在する場合（つまり葉ノードではない場合）はフラグを立て、最終的に子ノードを持たないノードのみを出力します。

ポイントは、再帰呼び出しの際に親ノードの情報を渡すことで、無向グラフとして構築した木の走査中に逆戻り（無限ループ）を防ぐ点です。

C++での実装例

以下のプログラムは、この解法の実装例です。

#include <bits/stdc++.h>
using namespace std;
void DFS(list<int> t[], int node, int parent) {
   int flag = 0;
   for (auto ir : t[node]) {
      if (ir != parent) {
         flag = 1;
         DFS(t, ir, node);
      }
   }
   if (flag == 0)
      cout<<node<<"\t";
}
int main() {
   list<int> t[1005];
   pair<int, int> edges[] = {
      { 1, 2 },
      { 1, 3 },
      { 2, 4 },
      { 3, 5 },
      { 3, 6 },
      { 3, 7 },
      { 6, 8 }
   };
   int cnt = sizeof(edges) / sizeof(edges[0]);
   int node = cnt + 1;
   for (int i = 0; i < cnt; i++) {
      t[edges[i].first].push_back(edges[i].second);
      t[edges[i].second].push_back(edges[i].first);
   }
   cout<<"Leaf nodes of the tree are:\n";
   DFS(t, 1, 0);
   return 0;
}

コードの解説

DFS関数では、現在のノードに隣接するノードを順番に調べます。隣接ノードの中に親ノード以外のものが存在すれば、そのノードは葉ではないためflagを1に設定し、再帰的にDFSを呼び出します。ループ終了後もflagが0のままの場合、そのノードには子が存在しない＝葉ノードであるため、値を出力します。

main関数では、辺のリストから隣接リスト形式のグラフ（木）を構築しています。無向木として両方向に辺を登録し、根ノード「1」からDFSを開始します。これにより、木全体を効率よく走査しながらすべての葉ノードを検出できます。

実行結果

Leaf nodes of the tree are −
4 5 8 7