মনে করুন একটি গ্রাফ আছে। আমাদের চেক করতে হবে গ্রাফটি স্ট্রংলি কানেক্টেড (Strongly Connected) কিনা Kosaraju অ্যালগরিদম ব্যবহার করে। একটি গ্রাফকে স্ট্রংলি কানেক্টেড বলা হয় যদি যেকোনো দুটি ভার্টেক্সের মধ্যে পথ থাকে, তবে গ্রাফটি কানেক্টেড। একটি আনডিরেক্টেড গ্রাফ স্ট্রংলি কানেক্টেড গ্রাফ।
কিছু আনডিরেক্টেড গ্রাফ কানেক্টেড হতে পারে কিন্তু স্ট্রংলি কানেক্টেড নয়। নিচে একটি স্ট্রংলি কানেক্টেড গ্রাফের উদাহরণ:
এটি কানেক্টেড কিন্তু স্ট্রংলি কানেক্টেড নয়:
Kosaraju অ্যালগরিদম ব্যবহার করে গ্রাফ স্ট্রংলি কানেক্টেড কিনা চেক করার ধাপগুলো:
- সকল নোডকে না-ভিজিটেড হিসেবে মার্ক করুন
- যেকোনো আרבিট্রারি ভার্টেক্স u থেকে DFS ট্রাভার্সাল শুরু করুন। যদি DFS সব নোড ভিজিট করতে না পারে, তবে false রিটার্ন করুন।
- গ্রাফের সকল এজ রিভার্স করুন
- সব ভার্টেক্সকে আবার না-ভিজিটেড হিসেবে সেট করুন
- উसी ভার্টেক্স u থেকে DFS ট্রাভার্সাল শুরু করুন। যদি DFS সব নোড ভিজিট করতে না পারে, তবে false রিটার্ন করুন, অন্যথায় true।
উদাহরণ কোড
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V;
list<int> *adj;
void dfs(int v, bool visited[]);
public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
~Graph() {
delete[] adj;
}
void addEdge(int v, int w);
bool isStronglyConnected();
Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
dfs(*i, visited);
}
Graph Graph::reverseArc() {
Graph graph(V);
for (int v = 0; v < V; v++) {
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
graph.adj[*i].push_back(v);
}
return graph;
}
void Graph::addEdge(int u, int v) {
adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph graph = reverseArc();
for (int i = 0; i < V; i++)
visited[i] = false;
graph.dfs(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
int main() {
Graph graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(2, 4);
graph.addEdge(4, 2);
graph.isStronglyConnected() ? cout << "This is strongly connected" : cout << "This is not strongly connected";
return 0;
}
আউটপুট
This is strongly connected
