C++で木（ツリー）のプリューファーコードを生成するプログラム

プリューファーコード（Prüfer Code）は、ラベル付きの木を一意な数列として表現できる符号化手法です。頂点に1からpまでのラベルが付けられた木（頂点数はユーザーが指定）を入力すると、長さ「p − 2」の数列が生成され、これによってその木を一意に識別できます。

プリューファーコードとは

n個のラベル付き頂点からなる木は、必ず長さ n−2 のプリューファーコードへ変換でき、逆にコードから元の木を復元することも可能です。この性質から、木の構造をコンパクトに扱う手段として広く知られており、有名なケイリーの公式（「n頂点のラベル付き木の総数は nⁿ⁻² 通り」）の証明にも利用されています。

アルゴリズムの流れ

基本となる考え方は以下のとおりです。

1. 各頂点の次数（接続されている辺の本数）を計算します。
2. 次数が1の頂点（葉）の中から、ラベル番号が最小のものを探します。
3. その頂点を木から取り除き、隣接していた頂点の番号をプリューファーコードに追加します。
4. 頂点が2つ残るまで、この操作を繰り返します。

疑似コード

開始
    i, j, ver, edg, minimum, p を整数型として宣言する
    「頂点の数を入力してください」と表示する
    ver の値を入力する
    edg = ver - 1 で初期化する
    EDG[edg][2] と DG[ver+1] を整数型として宣言し、DG[ver+1] = {0} で初期化する
    「この木は ○ 個の頂点に対して ○ 本の辺を持ちます」と表示する
    「入力が必要な頂点ペアは ○ 組です」と表示する
    for(i = 0; i < edg; i++)
        辺ごとの頂点ペアの入力を促すメッセージを表示する
        V(1) の値を EDG[i][0] へ、V(2) の値を EDG[i][1] へ入力する
        DG[EDG[i][0]]++ と DG[EDG[i][1]]++ で両頂点の次数を増やす
    「この木のプリューファーコードは: { 」と表示する
    for(i = 0; i < ver-2; i++)
        minimum = 10000 で初期化する
        for(j = 0; j < edg; j++)
            DG[EDG[j][0]] == 1 ならば、minimum > EDG[j][0] のとき minimum と p を更新
            DG[EDG[j][1]] == 1 ならば、minimum > EDG[j][1] のとき minimum と p を更新
        DG[EDG[p][0]]-- と DG[EDG[p][1]]-- で選択した辺を削除する
        DG[EDG[p][0]] == 0 ならば EDG[p][1] を出力、それ以外は EDG[p][0] を出力する
    「}」と表示する
終了

C++による実装例

#include<iostream>
using namespace std;
int main() {
   int i, j, ver, edg, minimum, p;
   cout<<"頂点の数を入力してください: ";
   cin>>ver;
   cout<<endl;
   edg = ver-1;
   int EDG[edg][2], DG[ver+1] = {0};
   cout<<"この木は "<<ver<<" 個の頂点に対して "<<edg<<" 本の辺を持ちます。\n";
   cout<<"入力が必要な頂点ペアは "<<edg<<" 組です。\n";
   for(i = 0; i < edg; i++) {
      cout<<"辺 "<<i+1<<" の頂点ペアを入力してください:\n";
      cout<<"V(1) の値: ";
      cin>>EDG[i][0];
      cout<<"V(2) の値: ";
      cin>>EDG[i][1];
      DG[EDG[i][0]]++;  // 片方の頂点の次数を増加
      DG[EDG[i][1]]++;  // もう片方の頂点の次数を増加
   }
   cout<<"\nこの木のプリューファーコードは: { "; // 与えられた木のプリューファーコードを出力
   for(i = 0; i < ver-2; i++) {
      minimum = 10000;
      for(j = 0; j < edg; j++) {
         if(DG[EDG[j][0]] == 1) {  // 次数が1の頂点（葉）を探す
            if(minimum > EDG[j][0]) {
               minimum = EDG[j][0];
               p = j;
            }
         }
         if(DG[EDG[j][1]] == 1) {
            if(minimum > EDG[j][1]) {
               minimum = EDG[j][1];
               p = j;
            }
         }
      }
      DG[EDG[p][0]]--; // 選択した頂点を削除するため、次数を減らしていく
      DG[EDG[p][1]]--; // 辺を削除したため、隣接頂点の次数も減らす
      if(DG[EDG[p][0]] == 0)
         cout<<EDG[p][1]<<" ";
      else
         cout<<EDG[p][0]<<" ";
   }
   cout<<"}";
   return 0;
}

実行例

頂点の数を入力してください: 5

この木は 5 個の頂点に対して 4 本の辺を持ちます。
入力が必要な頂点ペアは 4 組です。
辺 1 の頂点ペアを入力してください:
V(1) の値: 2
V(2) の値: 3
辺 2 の頂点ペアを入力してください:
V(1) の値: 5
V(2) の値: 6
辺 3 の頂点ペアを入力してください:
V(1) の値: 7
V(2) の値: 8
辺 4 の頂点ペアを入力してください:
V(1) の値: 9
V(2) の値: 10

この木のプリューファーコードは: { 4 8 4 }

処理のポイント

このプログラムでは、配列 DG[] で各頂点の次数を管理し、配列 EDG[][] で辺（頂点ペア）を保持しています。毎回のループで「次数が1かつラベルが最小の頂点」を選び出し、その頂点を削除しながら隣接頂点の番号を出力することで、プリューファーコードを順に構築していきます。計算量は O(n²) となり、頂点数がそこまで多くない場合には十分に実用的です。