C++ প্রোগ্রাম: দুই নোডের মধ্যে পাথ আছে কিনা চেক করা

এটি একটি C++ প্রোগ্রাম যা দুই দেওয়া নোডের মধ্যে পাথ আছে কিনা তা খুঁজে বের করে।

অ্যালগরিদম

শুরু
  ফাংশন isReach() হল একটি রিকার্সিভ ফাংশন যা চেক করে d, s-থেকে erreich্য কিনা:
  A) সব ভার্টেক্সকে অনভিজিটেড হিসেবে মার্ক করুন।
  B) বর্তমান নোডকে ভিজিটেড মার্ক করুন এবং এনকিউ করুন এবং এটি একটি ভার্টেক্সের সব সন্নিহিত ভার্টেক্স পেতে ব্যবহার হবে।
  C) কিউ থেকে একটি ভার্টেক্স ডিকিউ করুন এবং প্রিন্ট করুন।
  D) ডিকিউ করা ভার্টেক্স s-এর সব সন্নিহিত ভার্টেক্স পান।
  E) যদি একটি সন্নিহিত নোড ভিজিটেড না থাকে, তবে এটি ভিজিটেড মার্ক করুন এবং এনকিউ করুন।
  F) যদি এই সন্নিহিত নোড গন্তব্য নোড হয়, তবে true রিটার্ন করুন অন্যথায় BFS চালিয়ে যান।
শেষ

উদাহরণ

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

class G {
    int n;
    list<int> *adj;
public:
    G(int n);
    void addEd(int x, int w);
    bool isReach(int s, int d);
};

G::G(int n) { // কনস্ট্রাক্টর
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int x, int w) { // গ্রাফে এজ যোগ করা
    adj[x].push_back(w); // w কে x-এর লিস্টে যোগ করুন
}

bool G::isReach(int s, int d) {
    if (s == d)
        return true;
    bool* visited = new bool[n];
    // সব ভার্টেক্সকে অনভিজিটেড হিসেবে মার্ক করুন।
    for (int i = 0; i < n; 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() {
    G g(4);
    g.addEd(1, 3);
    g.addEd(0, 1);
    g.addEd(2, 3);
    g.addEd(1, 0);
    g.addEd(2, 1);
    g.addEd(3, 1);
    cout << "Enter the source and destination vertices: (0-3)";
    int a, b;
    cin >> a >> b;
    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;
    int t;
    t = a;
    a = b;
    b = t;
    if (g.isReach(a, b))
        cout << "\nThere is a path from " << a << " to " << b;
    else
        cout << "\nThere is no path from " << a << " to " << b;
    return 0;
}

আউটপুট

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