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

এই প্রোগ্রামে DFS ব্যবহার করে একটি গ্রাফে দুটি নোডের মধ্যে পথ আছে কিনা তা চেক করা হয়।

অ্যালগরিদম

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

উদাহরণ

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

class G {
    int n;
    list *adj;
public:
    G(int n);
    void addEd(int v, int u);
    bool isReach(int s, int d);
};

G::G(int n) {
    this->n = n;
    adj = new list[n];
}

void G::addEd(int v, int u) {
    adj[v].push_back(u);
}

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 queue;
    visited[s] = true;
    queue.push_back(s);
    list::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 = 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