C++のすべてのノードを訪問する最短経路

N個のノードを持つ1つの無向の連結グラフがあると仮定します。これらのノードには、0、1、2、...、N-1のラベルが付けられます。グラフの長さはNになり、ノードiとjが接続されている場合に限り、jはリストgraph[i]にあるiと同じではありません。すべてのノードを訪問する最短経路の長さを見つける必要があります。任意のノードで開始および停止でき、ノードを複数回再訪でき、エッジを再利用できます。

したがって、入力が[[1]、[0,2,4]、[1,3,4]、[2]、[1,2]]の場合、出力は4になります。パスは[0,1,4,2,3]です。

これを解決するには、次の手順に従います-

• 1つのキューを定義する

• n：=グラフのサイズ

• req：=2 ^（n-1）

• 1つのマップを定義する

• 初期化i：=0の場合、i

  • {0 OR（2 ^ i）、i}をq

    に挿入します

• nが1と同じ場合、-

  • 0を返す

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szがゼロ以外の場合、反復ごとにszを1ずつ減らし、-

    を実行します。

    • 配列curr=qのフロント要素を定義します

    • qから要素を削除

    • 初期化i：=0の場合、i<グラフのサイズ[curr[1]]の場合、更新（iを1増やします）、実行

      • u：=グラフ[curr [1]、i]

      • newMask：=（curr[0]または2^ u）

      • newMaskがreqと同じ場合、-

        • レベルを返す

      • visited[u]のcallcount（newMask）の場合、-

        • 次の部分を無視し、次の反復にスキップします

      • newMaskをvisited[u]

        に挿入します

      • {newMask、u}をq

        に挿入します

• -1を返す

理解を深めるために、次の実装を見てみましょう-

例

#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