C++で解くピーターセングラフのウォーク問題：文字列を実現する辞書順最小の経路を求める

問題の概要

下図のようなグラフを考えます。これは有名なピーターセングラフです。頂点には0から9までの番号が振られており、各頂点には特定の文字が割り当てられています。

このグラフ上のウォーク（歩行）Wを考えます。WはL個の頂点を使用します。長さLの文字列SがウォークWによって実現されるとは、Wで訪問した頂点に割り当てられた文字の並びがSと一致することを指します。なお、同じ頂点を何度訪問しても構いません。

例えば、文字列Sが「ABBECCD」の場合、これはウォーク(0, 1, 6, 9, 7, 2, 3)によって実現されます。

私たちのタスクは、与えられた文字列を実現するウォークを見つけることです。そのようなウォークが存在する場合は辞書順で最小のものを出力し、存在しない場合は-1を返します。

ピーターセングラフの構造

ピーターセングラフは、外側の五角形（頂点0〜4）、内側の星型（頂点5〜9）、そして両者を結ぶ5本のスポークから構成されます。各文字（A〜E）は外周の頂点と内側の頂点の2か所に対応しているため、文字列をたどる際にどちらの頂点を選ぶかがポイントになります。

アルゴリズム

ここでは貪欲法（グリーディ法）を用います。開始頂点を決めた後、文字列の2文字目以降について、まず外周グラフ（番号の小さい頂点）への移動を試み、不可能なら内側グラフ（c+5の頂点）への移動を試みます。どちらにも移動できない場合は、その文字列は実現できません。

begin
    res := 開始頂点
    S の先頭以外の各文字 c について繰り返し:
        もし外周グラフで v と c の間に辺があれば
            v := c
        そうでなければ、内側グラフで v と c+5 の間に辺があるなら
            v := c + 5
        どちらでもなければ
            false を返す
        end if
        v を res に追加
    done
    true を返す
end

辞書順最小のウォークを得るため、開始頂点としては外周の頂点（小さい番号）を優先的に試します。これにより、各ステップで可能な限り小さい頂点番号が選ばれ、結果として全体で辞書順最小の経路が得られます。

C++による実装例

#include<iostream>
using namespace std;
// ピーターセングラフの隣接行列
bool adj_mat[10][10] = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0, 1, 0, 0},
    {0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
    {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 1, 0, 0, 1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 1, 0, 0}
};
char S[100005];
char res[100005];
bool petersonGraphWalk(char* S, int v){
    res[0] = v + '0';
    for(int i = 1; S[i]; i++){
       // まず外周グラフを探索
       if(adj_mat[v][S[i] - 'A'] || adj_mat[S[i] - 'A'][v]){
           v = S[i] - 'A';
       }
       // 次に内側グラフを確認
       else if(adj_mat[v][S[i] - 'A' + 5] || adj_mat[S[i] - 'A' + 5][v]){
           v = S[i] - 'A' + 5;
       }else{
           return false;
       }
       res[i] = v + '0';
    }
    return true;
}
main() {
    char* str = "ABBECCD";
    if(petersonGraphWalk(str, str[0] - 'A') || petersonGraphWalk(str, str[0] - 'A' + 5)){
        cout << res;
    }else{
        cout << -1;
    }
}

実行結果

0169723

文字列「ABBECCD」に対して、ウォーク(0, 1, 6, 9, 7, 2, 3)が出力されました。これは辞書順最小の解となっています。プログラムでは、まず外周の開始頂点（0）から探索を試み、失敗した場合のみ内側の開始頂点（5）を試すことで、常に辞書順最小のウォークが保証されます。