C++ এ সমস্ত নোড দেখার সংক্ষিপ্ততম পথ

ধরুন আমাদের N নোডগুলির সাথে একটি অনির্দেশিত, সংযুক্ত গ্রাফ রয়েছে এই নোডগুলিকে 0, 1, 2, ..., N-1 হিসাবে লেবেল করা হয়েছে। গ্রাফের দৈর্ঘ্য হবে N, এবং j একই নয় যেমন i তালিকার গ্রাফে আছে[i] ঠিক একবার, যদি এবং শুধুমাত্র যদি নোড i এবং j সংযুক্ত থাকে। আমাদের প্রতিটি নোড পরিদর্শনকারী সংক্ষিপ্ততম পথের দৈর্ঘ্য খুঁজে বের করতে হবে। আমরা যেকোন নোডে শুরু করতে এবং থামাতে পারি, আমরা একাধিকবার নোডগুলি পুনরায় দেখতে পারি এবং আমরা প্রান্তগুলি পুনরায় ব্যবহার করতে পারি৷

সুতরাং, যদি ইনপুটটি [[1],[0,2,4],[1,3,4],[2],[1,2]] এর মত হয়, তাহলে আউটপুট হবে 4। এখন এখানে একটি সম্ভব। পথ হল [0,1,4,2,3]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি সারি সংজ্ঞায়িত করুন

• n :=গ্রাফের আকার

• req :=2^(n - 1)

• একটি মানচিত্র সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • q

    -এ {0 বা (2^i), i} ঢোকান

• যদি n 1 এর সমান হয়, তাহলে −

  • রিটার্ন 0

• lvl শুরু করার জন্য :=1, যখন q খালি না থাকে, আপডেট করুন (lvl 1 দ্বারা বাড়ান), করুন −

  • sz :=q এর আকার

  • যখন sz অ-শূন্য হয়, প্রতিটি পুনরাবৃত্তিতে 1 দ্বারা sz কমান, −

    • একটি অ্যারে curr =q এর সামনের উপাদান

      সংজ্ঞায়িত করুন

    • q

      থেকে উপাদান মুছুন

    • আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার[curr[1]], আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন

      • u :=গ্রাফ[curr[1], i]

      • newMask :=(curr[0] বা 2^u)

      • যদি newMask req এর মত হয়, তাহলে −

        • ফিরুন lvl

      • যদি পরিদর্শন করা [u] কল কাউন্ট(নতুন মাস্ক) হয়, তাহলে -

        • নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান

      • ভিজিট করা[u]

        -এ নতুন মাস্ক ঢোকান

      • q

        -এ {newMask, u} ঢোকান

• রিটার্ন -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