C++ প্রোগ্রাম: ডাইরেক্টেড গ্রাফ Weakly Connected নাকি Strongly Connected চেক করা

একটি ডাইরেক্টেড গ্রাফ Weakly Connected নাকি Strongly Connected তা DFS ব্যবহার করে বের করা যায়।

ব্যবহৃত ফাংশন

Begin
    Function fillorder() = সব ভার্টেক্স স্ট্যাকে পুশ করুন।
    a) বর্তমান নোডকে ভিজিটেড মার্ক করুন।
    b) এই ভার্টেক্সের সাথে অadyacent সকল ভার্টেক্সের জন্য রিকার্সিভ কল করুন।
    c) v-থেকে পৌঁছানো সকল ভার্টেক্স প্রসেসড হলে, v-কে স্ট্যাকে পুশ করুন।
End
Begin
    Function DFS():
    a) বর্তমান নোডকে ভিজিটেড মার্ক করুন।
    b) এই ভার্টেক্সের সাথে অadyacent সকল ভার্টেক্সের জন্য রিকার্সিভ কল করুন।
End

উদাহরণ

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

class G {
    int m;
    list *adj;
    void fillOrder(int n, bool visited[], stack &Stack);
    void DFS(int n, bool visited[]);
public:
    G(int N);
    void addEd(int v, int w);
    int print();
    G getTranspose();
};

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

void G::DFS(int n, bool visited[]) {
    visited[n] = true;
    cout << n << " ";
    list::iterator i;
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFS(*i, visited);
}

G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i)
            g.adj[*i].push_back(n);
    }
    return g;
}

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

void G::fillOrder(int v, bool visited[], stack &Stack) {
    visited[v] = true;
    list::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            fillOrder(*i, visited, Stack);
    Stack.push(v);
}

int G::print() {
    stack Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++) visited[i] = false;
    for (int i = 0; i < m; i++)
        if (visited[i] == false)
            fillOrder(i, visited, Stack);
    G graph = getTranspose();
    for (int i = 0; i < m; i++) visited[i] = false;
    int count = 0;
    while (Stack.empty() == false) {
        int v = Stack.top();
        Stack.pop();
        if (visited[v] == false) {
            graph.DFS(v, visited);
            cout << endl;
        }
        count++;
    }
    return count;
}

int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);
    cout << "Following are strongly connected components in given graph \n";
    if (g.print() > 1)
        cout << "Graph is weakly connected.";
    else
        cout << "Graph is strongly connected.";
    return 0;
}

আউটপুট

Following are strongly connected components in given graph
4
0 1 2 3
Graph is weakly connected.