सभी नोड्स देखने वाला सबसे छोटा पथ 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]।

हल करने का दृष्टिकोण

हम बिटमास्क के साथ BFS का उपयोग करते हैं:

• स्थिति = (मास्क, नोड) जहां मास्क देखे गए नोड्स को दर्शाता है

• प्रत्येक नोड से मास्क = 1<<नोड के साथ शुरू करें

• आवश्यक मास्क = (1<

• प्रत्येक स्थिति के लिए, सभी पड़ोसियों का पता लगाएं

• नया_मास्क = मास्क | (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; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}}; 
    cout << (ob.shortestPathLength(v)); 
    return 0;
}

इनपुट

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

आउटपुट

4