C++でグラフの全ノードを訪問する最短経路の長さを求める方法

無向かつ連結なグラフがあり、N 個のノードには 0, 1, 2, ..., N-1 の番号が付けられているものとします。配列 graph の長さは N であり、graph[i] にはノード i と直接接続しているノード j（i ≠ j）がちょうど一度だけ含まれます。この課題では、すべてのノードを訪問する最短経路の長さを求めます。開始地点と終了地点は任意のノードを選べるほか、同じノードや辺を何度でも再訪問・再利用できる点が特徴です。

たとえば、入力が [[1],[0,2,4],[1,3,4],[2],[1,2]] の場合、答えは 4 になります。このとき [0, 1, 4, 2, 3] という経路が一つの解となります。

解法の考え方：ビットマスク＋幅優先探索（BFS）

この問題は、各時点での「訪問済みノードの集合」をビットマスクで管理しながら幅優先探索（BFS）を行うことで、効率的に解くことができます。具体的な手順は以下の通りです。

• キューをひとつ用意します。
• n := グラフのノード数とします。
• req := 2^n − 1 とします（すべてのノードを訪問済みにした状態を表すビットマスクです）。
• 訪問状態を記録するためのマップ（visited）を定義します。
• i = 0 ～ n−1 の各ノードについて、{0 OR 2^i, i}（そのノードのみ訪問済みのマスクとノード番号のペア）をキューに挿入します。
• n が 1 の場合は 0 を返します。
• キューが空になるまで、探索レベル（lvl）ごとに次を繰り返します。
  • sz := 現在のキューのサイズとし、sz 回だけ以下を処理します。
    • curr := キューの先頭要素を取り出します。
    • curr[1]（現在のノード）に隣接する各ノード u について処理します。
      • u := graph[curr[1]][i] とします。
      • newMask := curr[0] OR 2^u（u を新たに訪問済みにしたマスク）とします。
      • newMask が req と等しければ、lvl（現在の移動回数）を返します。これが答えです。
      • visited[u] に newMask が既に存在する場合は、以降をスキップします。
      • newMask を visited[u] に追加し、{newMask, u} をキューに挿入します。
• ループを抜けた場合は −1 を返します（連結グラフのため実際には起こりません）。

重要なポイント

この解法の鍵は、単純な「ノードの訪問済み判定」ではなく、（訪問済みマスク, 現在位置）のペアをひとつの状態として扱い、重複を排除することです。同じノードにいても、そこへ至るまでの訪問履歴（マスク）が異なれば別々の状態として管理する必要があります。また、BFS はレベルごとに近い経路から順に探索するため、最初に req に到達した時点の lvl が必ず最短距離になります。

計算量は状態数が高々 2^N × N 通りであることから、時間・空間ともに O(2^N × N) となり、N が小さい制約下で十分高速に動作します。

それでは、理解を深めるために実装を見てみましょう。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   int shortestPathLength(vector<vector<int> >& graph){
      queue<vector<int> > q;
      int n = graph.size();
      int req = (1 << n) - 1;
      map<int, set<int> > visited;
      for (int i = 0; i < n; i++) {
         q.push({ 0 | (1 << i), i });
      }
      if (n == 1)
      return 0;
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            vector<int> curr = q.front();
            q.pop();
            for (int i = 0; i < graph[curr[1]].size(); i++) {
               int u = graph[curr[1]][i];
               int newMask = (curr[0] | (1 << u));
               if (newMask == req)
                  return lvl;
               if (visited[u].count(newMask))
               continue;
               visited[u].insert(newMask);
               q.push({ newMask, u });
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}};
   cout << (ob.shortestPathLength(v));
}

入力

{{1},{0,2,4},{1,3,4},{2},{1,2}}

出力

4