একটি ডায়রেক্টেড গ্রাফকে স্ট্রংলি কানেক্টেড বলা হয়, যখন একটি কম্পোনেন্টের প্রতিটি ভার্টেক্স জোড়ার মধ্যে একটি পথ থাকে।
এই অ্যালগরিদম সমাধান করতে, প্রথমে DFS অ্যালগরিদম ব্যবহার করা হয় প্রতিটি ভার্টেক্সের ফিনিশ টাইম পেতে, তারপর ট্রান্সপোজড গ্রাফের ফিনিশ টাইম বের করা হয়, তারপর ভার্টেক্সগুলোকে টপোলজিক্যাল সোর্ট দিয়ে ডিসেন্ডিং অর্ডারে সর্ট করা হয়।
ইনপুট এবং আউটপুট
ইনপুট: গ্রাফের অ্যাডজেসেন্সি ম্যাট্রিক্স। 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 আউটপুট: প্রদত্ত গ্রাফে স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো: 0 1 2 3 4
এলগরিদম
traverse(graph, start, visited)
ইনপুট: ট্রাভার্স করা গ্রাফ, শুরুর ভার্টেক্স, এবং ভিজিটেড নোডের ফ্ল্যাগ।
আউটপুট: DFS টেকনিক দিয়ে প্রতিটি নোডের মধ্য দিয়ে যান এবং নোডগুলো প্রদর্শন করুন।
শুরু
start কে ভিজিটেড চিহ্নিত করুন
start-র সাথে সংযুক্ত সব ভার্টেক্স v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
traverse(graph, v, visited)
শেষ লুপ
শেষ
topoSort(u, visited, stack)
ইনপুট: শুরুর নোড, ভিজিটেড ভার্টেক্সের ফ্ল্যাগ, স্ট্যাক।
আউটপুট: গ্রাফ সর্ট করার সময় স্ট্যাক পূরন করুন।
শুরু
u কে ভিজিটেড চিহ্নিত করুন
u-র সাথে সংযুক্ত সব নোড v এর জন্য, করুন
যদি v ভিজিটেড না থাকে, তবে
topoSort(v, visited, stack)
শেষ লুপ
u কে স্ট্যাকে পুশ করুন
শেষ
getStrongConComponents(graph)
ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: সব স্ট্রংলি কানেক্টেড কম্পোনেন্ট।
শুরু
প্রাথমিকভাবে সব নোড অনভিজিটেড
গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
যদি i ভিজিটেড না থাকে, তবে
topoSort(i, vis, stack)
শেষ লুপ
আবার সব নোডকে অনভিজিটেড করুন
transGraph := প্রদত্ত গ্রাফের ট্রান্সপোজ
যতক্ষণ স্ট্যাক খালি নয়, করুন
স্ট্যাক থেকে নোড পপ করুন এবং v-তে নিন
যদি v ভিজিটেড না থাকে, তবে
traverse(transGraph, v, visited)
শেষ লুপ
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <stack>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 0, 1, 1, 0},
{1, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int transGraph[NODE][NODE];
void transpose() {
// গ্রাফকে ট্রান্সপোজ করুন এবং transGraph-এ স্টোর করুন
for(int i = 0; i < NODE; i++)
for(int j = 0; j < NODE; j++)
transGraph[i][j] = graph[j][i];
}
void traverse(int g[NODE][NODE], int u, bool visited[]) {
visited[u] = true; // v কে ভিজিটেড চিহ্নিত করুন
cout << u << " ";
for(int v = 0; v < NODE; v++) {
if(g[u][v]) {
if(!visited[v])
traverse(g, v, visited);
}
}
}
void topoSort(int u, bool visited[], stack<int> &stk) {
visited[u] = true; // নোড v কে ভিজিটেড হিসেবে সেট করুন
for(int v = 0; v < NODE; v++) {
if(graph[u][v]) { // u-র সাথে সংলগ্ন সব ভার্টেক্স v এর জন্য
if(!visited[v])
topoSort(v, visited, stk);
}
}
stk.push(u); // শুরুর ভার্টেক্সকে স্ট্যাকে পুশ করুন
}
void getStrongConComponents() {
stack<int> stk;
bool vis[NODE];
for(int i = 0; i < NODE; i++)
vis[i] = false; // প্রাথমিকভাবে সব নোড অনভিজিটেড
for(int i = 0; i < NODE; i++)
if(!vis[i]) // যখন নোড ভিজিটেড নয়
topoSort(i, vis, stk);
for(int i = 0; i < NODE; i++)
vis[i] = false; // ট্রাভার্সালের জন্য সব নোডকে অনভিজিটেড করুন
transpose(); // রিভার্সড গ্রাফ তৈরি করুন
while(!stk.empty()) {
// যখন স্ট্যাকে উপাদান থাকে, টপোলজিক্যাল অর্ডারে প্রসেস করুন
int v = stk.top(); stk.pop();
if(!vis[v]) {
traverse(transGraph, v, vis);
cout << endl;
}
}
}
int main() {
cout << "Following are strongly connected components in given graph: " << endl;
getStrongConComponents();
}
আউটপুট
Following are strongly connected components in given graph: 0 1 2 3 4
