C++ में BFS का उपयोग करके एक शीर्ष से शेष सभी शीर्षों तक पथ खोजना

समस्या विवरण

इस समस्या में, हमें एक निर्देशित ग्राफ दिया गया है जिसे आसन्न सूची के रूप में दर्शाया गया है। हमारा कार्य BFS का उपयोग करके एक शीर्ष से शेष सभी शीर्षों तक पथ खोजने के लिए एक प्रोग्राम बनाना है।

BFS (ब्रेडथ फर्स्ट सर्च) एक एल्गोरिदम है जो ग्राफ को ब्रेडथवार्ड मोशन में पार करता है और अगले शीर्ष को याद रखने के लिए एक क्यू का उपयोग करता है जहां से खोज शुरू करनी है, जब किसी पुनरावृत्ति में डेड एंड होता है।

उदाहरण

इनपुट - ग्राफ:

आउटपुट

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

समस्या को हल करने के लिए, हम ग्राफ के प्रत्येक तत्व पर BFS खोज एल्गोरिदम करेंगे। कार्य करने के लिए, हम एक क्यू बनाएंगे जो किसी भी नोड पर विजिट के लिए फ्लैग संग्रहीत करेगा। फिर, एक विज़िटेड सरणी का उपयोग करके हम जांचेंगे कि तत्व विज़िट किया गया है या नहीं (बाइनरी मान 0 और 1 विजिट को दर्शाते हैं)।

चरण-दर-चरण निष्पादन

नोड 0 से शुरू:

सीधे नोड 1 पर जाएं
नोड 2 तक पहुंचने के लिए, पहले नोड 1 पर जाएं फिर नोड 1 को पार करके नोड 2 तक पहुंचें
नोड 3 तक पहुंचने के लिए, 0 से सीधे 3 पर जाएं
नोड 4 तक पहुंचने के लिए, पहले नोड 3 पर जाएं फिर नोड 4

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

void printPath(vector<int> parent, int initial, int node) {
    vector<int> path;
    while (node != initial) {
        path.push_back(node);
        node = parent[node];
    }
    path.push_back(initial);
    reverse(path.begin(), path.end());
    
    for (int i = 0; i < path.size(); i++) {
        if (i > 0) cout << " ← ";
        cout << path[i];
    }
    cout << endl;
}

void findPathBFS(vector<vector<int>> graphAdjList, int initial, int graphSize) {
    vector<int> parent(graphSize, -1);
    vector<int> visited(graphSize, 0);
    queue<int> q;
    
    visited[initial] = 1;
    parent[initial] = initial;
    q.push(initial);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graphAdjList[u]) {
            if (!visited[v]) {
                visited[v] = 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    for (int k = 0; k < graphSize; k++) {
        if (visited[k])
            printPath(parent, initial, k);
        else
            cout << k << " (अप्राप्य)" << endl;
    }
}

int main() {
    vector<vector<int>> graphAdjList;
    graphAdjList.push_back({1, 3});
    graphAdjList.push_back({0, 2});
    graphAdjList.push_back({1});
    graphAdjList.push_back({4});
    graphAdjList.push_back({0});
    
    int graphSize = graphAdjList.size();
    int initial = 0;
    cout << "शीर्ष '0' से ग्राफ में अन्य सभी शीर्षों तक पथ है:\n";
    findPathBFS(graphAdjList, initial, graphSize);
    return 0;
}

आउटपुट

शीर्ष '0' से ग्राफ में अन्य सभी शीर्षों तक पथ है:
0
1 ← 0
2 ← 1 ← 0
3 ← 0
4 ← 3 ← 0

जटिलता विश्लेषण

समय जटिलता: O(V + E)
स्पेस जटिलता: O(V)

मुख्य बिंदु

BFS अनभारित ग्राफ में सबसे छोटा पथ (किनारों की संख्या के संदर्भ में) खोजता है
पैरेंट सरणी पथ पुनर्निर्माण को सक्षम बनाती है
अप्राप्य नोड्स का पैरेंट -1 रहता है