सी++ में सभी नोड्स का दौरा करने वाला सबसे छोटा पथ

मान लीजिए कि हमारे पास एन नोड्स के साथ एक अप्रत्यक्ष, जुड़ा हुआ ग्राफ है, इन नोड्स को 0, 1, 2, ..., एन -1 के रूप में लेबल किया गया है। ग्राफ़ की लंबाई N होगी, और j वैसा नहीं है जैसा मैं सूची में है ग्राफ़ [i] ठीक एक बार, यदि और केवल यदि नोड्स i और j जुड़े हुए हैं। हमें प्रत्येक नोड पर जाने वाले सबसे छोटे पथ की लंबाई ज्ञात करनी होगी। हम किसी भी नोड पर शुरू और बंद कर सकते हैं, हम कई बार नोड्स पर फिर से जा सकते हैं, और हम किनारों का पुन:उपयोग कर सकते हैं।

तो, अगर इनपुट [[1],[0,2,4], [1,3,4], [2], [1,2]] जैसा है, तो आउटपुट 4 होगा। अब यहां एक संभव है पथ [0,1,4,2,3] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक कतार परिभाषित करें

• n :=ग्राफ़ का आकार

• अनुरोध :=2^(n - 1)

• एक मानचित्र परिभाषित करें

• इनिशियलाइज़ i :=0 के लिए, जब i

  • q में {0 OR (2^i), i} डालें

• यदि n 1 के समान है, तो -

  • वापसी 0

• lvl को इनिशियलाइज़ करने के लिए:=1, जब q खाली न हो, तो अपडेट करें (lvl को 1 से बढ़ाएँ), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz को 1 से घटाएं, करें -

    • एक सरणी को परिभाषित करें curr =q का अगला तत्व

    • q से तत्व हटाएं

    • प्रारंभ करने के लिए मैं:=0, जब मैं <ग्राफ का आकार [कर्र [1]], अद्यतन (मैं 1 से बढ़ाएँ), करते हैं

      • यू:=ग्राफ [कर्र [1], आई]

      • न्यूमास्क:=(करंट[0] या 2^यू)

      • अगर न्यूमास्क रिक के समान है, तो -

        • वापसी एलवीएल

      • अगर विज़िट किए गए [यू] की कॉल काउंट (न्यूमास्क) है, तो −

        • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

      • विज़िट किए गए[u]

        . में newMask डालें

      • 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