একটি ডিরেক্টেড গ্রাফের উইকলি বা স্ট্রাংলি কানেক্টেড কিনা তা DFS ব্যবহার করে বের করা যায়। এটি সি++ প্রোগ্রাম।
ব্যবহৃত ফাংশন
Begin Function fillorder() = স্টকে সব ভার্টেক্স পুশ করুন।
a) বর্তমান নোডকে ভিজিটেড মার্ক করুন এবং প্রিন্ট করুন
b) এই ভার্টেক্সের সাথে সন্নিহিত সব ভার্টেক্সের জন্য রিকার্শন
c) v থেকে পৌঁছানো যাবে সব ভার্টেক্স প্রসেসড হলে, v-কে Stack-এ পুশ করুন
End
Begin Function DFS() :
a) বর্তমান নোডকে ভিজিটেড মার্ক করুন এবং প্রিন্ট করুন
b) এই ভার্টেক্সের সাথে সন্নিহিত সব ভার্টেক্সের জন্য রিকার্শন
End
উদাহরণ
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
int m;
list<int> *adj;
void fillOrder(int n, bool visited[], stack<int> &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<int>[m];
}
void G::DFS(int n, bool visited[]) {
visited[n] = true;
cout << n << " ";
list<int>::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<int>::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<int> &Stack) {
visited[v] = true;
list<int>::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<int> 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.
