নির্দেশিত গ্রাফে কম্পোনেন্টগুলো স্ট্রংলি কানেক্টেড বলা হয় যখন এক কম্পোনেন্টের প্রতিটি ভার্টেক্স জোড়ার মাঝপথে পথ থাকে।
এই অ্যালগরিদম সমাধান করতে প্রথমে 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)
শেষ
শেষ
উদাহরণ কোড
#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() {
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;
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;
for(int v = 0; v < NODE; v++) {
if(graph[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
