C++ प्रोग्राम: दो नोड्स के बीच पथ की जांच (BFS)

यह C++ प्रोग्राम Breadth-First Search (BFS) एल्गोरिदम का उपयोग करके निर्धारित करता है कि एक डायरेक्टेड ग्राफ में दो दिए गए नोड्स के बीच कोई पथ मौजूद है या नहीं।

एल्गोरिदम

शुरुआत
  1. फंक्शन isReach() रिकर्सिव फंक्शन है जो जांचता है कि d, s से पहुंच योग्य है या नहीं:
     A) सभी वर्टेक्स को अनविजिटेड मार्क करें।
     B) वर्तमान नोड को विजिटेड मार्क करें और एनक्यू करें।
     C) क्यू से एक वर्टेक्स डीक्यू करें।
     D) डीक्यू किए गए वर्टेक्स के सभी आसन्न वर्टेक्स प्राप्त करें।
     E) यदि कोई आसन्न वर्टेक्स अनविजिटेड है, तो उसे विजिटेड मार्क करें और एनक्यू करें।
     F) यदि यह आसन्न नोड डेस्टिनेशन नोड है, तो true लौटाएं, अन्यथा BFS जारी रखें।
समाप्ति

उदाहरण कोड

#include <iostream>
#include <list>
using namespace std;

class Graph {
    int V;
    list<int> *adj;
    
public:
    Graph(int V);
    void addEdge(int v, int w);
    bool isReachable(int s, int d);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // w को v की लिस्ट में जोड़ें
}

bool Graph::isReachable(int s, int d) {
    if (s == d) return true;
    
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) visited[i] = false;
    
    list<int> queue;
    visited[s] = true;
    queue.push_back(s);
    
    list<int>::iterator i;
    
    while (!queue.empty()) {
        s = queue.front();
        queue.pop_front();
        
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (*i == d) return true;
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    return false;
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    
    cout << "Enter source and destination vertices (0-3): ";
    int a, b;
    cin >> a >> b;
    
    if (g.isReachable(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;
    
    // रिवर्स दिशा भी जांचें
    int temp = a;
    a = b;
    b = temp;
    
    if (g.isReachable(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;
    
    return 0;
}

आउटपुट

Enter source and destination vertices (0-3): 3 1
There is a path from 3 to 1
There is a path from 1 to 3

समय जटिलता: O(V + E) जहां V वर्टेक्स की संख्या है और E एज की संख्या है।

स्पेस जटिलता: O(V) विजिटेड ऐरे और क्यू के लिए।